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

思路是先遍历树，找到整个树中与target之间差值，然后将差值从小到大排序依次填入数组中，最后要求非降序，重新排一下数组即可，该方法有优化空间

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
#include <utility>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param target double浮点型 
     * @param m int整型 
     * @return int整型vector
     */
    struct VarType{
        int tree;
        double diff;
    };
    static bool compare_func(struct VarType val1,struct VarType val2){
        return fabs(val1.diff)<fabs(val2.diff);
    }

    void trsv(vector<struct VarType>& res,TreeNode* root,double target){
        // pair<int, double> tmp;
        struct VarType tmp;
        if(root==nullptr) return;
        tmp.tree=root->val;
        tmp.diff=static_cast<double>(root->val)-target;
        res.push_back(tmp);
        trsv(res, root->left, target);
        trsv(res, root->right, target);
    }

    vector<int> findClosestElements(TreeNode* root, double target, int m) {
        // write code here
        vector<int> res;
        vector<VarType> pairs;
        trsv(pairs, root, target);
        if(m>pairs.size()) return res;
        sort(pairs.begin(), pairs.end(), compare_func);
        for (int i=0; i<m; i++) {
            res.push_back(pairs[i].tree);
        }
        sort(res.begin(),res.end());
        return res;
    }
};