题解 | #牛牛的二叉树问题#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <functional>
#include <vector>
struct AbsCompare {
    static double target;
    bool operator()(int a, int b) const {
        return std::abs(a - target) < std::abs(b - target);
    }
};
class Solution {

  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param target double浮点型
     * @param m int整型
     * @return int整型vector
     */



 
    vector<int> findClosestElements(TreeNode* root, double target, int m) {
        // write code here
        
        auto compare = [&target](int a, int b) {
                return abs(a-target) < abs(b-target); // 降序排列
        };
        priority_queue<int, std::vector<int>, decltype(compare)> minHeap(compare);
        function<void(TreeNode *)> dfs=[&minHeap,&m,&target ,&dfs](TreeNode * node){
             if (node) {
                
                double dist = abs(node->val - target);
                if (minHeap.size() < m) {
                    minHeap.push(node->val);
                } else {
                    // cout<<target<<'\t'<<maxHeap.top()<<'\t'<<node->val<<endl;
                    if (abs(minHeap.top() - target) > dist ) {
                        // cout<<maxHeap.top();
                        minHeap.pop();
                        minHeap.push(node->val);
                    }
                }
                dfs(node->left);
                dfs(node->right);
            }
        };
        dfs(root);

        vector<int> res;
        while (!minHeap.empty()) {
            res.push_back(minHeap.top());
            minHeap.pop();
        }
        sort(res.begin(), res.end());

        return res;
    }
};

使用最小堆来获取m个最小距离节点