Simple c++ solution


  • 0
    S
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode *node;
        map< TreeNode*, vector<TreeNode*> > m;
        
        int ans;
        int dis = INT_MAX;
        
        int findClosestLeaf(TreeNode* root, int k) {
            buildMap(root, nullptr, k);
            vector<TreeNode*>  v = m[node];
    
            if(isLeaf(node) ) {
                return k;
            }
            findMin(0, node, node, k);
            return ans;
        }
        
       
        void findMin(int add, TreeNode * current, TreeNode * pre, int k){
            if(add > dis){
                return;
            }
            vector<TreeNode*> v = m[current];
            if(isLeaf(current) ){
                if(add < dis){
                    dis = add;
                    ans = current->val;
                }
                return;
            }
            int val = INT_MAX;
            for(TreeNode * t : v){
                if(t->val != pre->val ){
                    findMin(add + 1,  t , current, k);
                }
            }
            return;
        }
       
        bool isLeaf(TreeNode * n){
            return !n->left && !n->right;
        }
        
        
        void buildMap(TreeNode *root, TreeNode *parent, int k){
            if(node == nullptr && root->val == k){
                node = root;
            }
            vector<TreeNode*> v;
            if(parent){
                v.push_back(parent);
            }
            if(root->left){
                v.push_back(root->left);
                buildMap(root->left, root, k);
            }
            if(root->right){
                v.push_back(root->right);
                buildMap(root->right, root, k);
            }
            m[root] = v;
        }
        
        
    };
    

  • 0
    W

    I ran your solution, but it can not pass the example. It's supposed to output 2, but instead your output is 3.-


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.