863. 二叉树中所有距离为 K 的结点

863. 二叉树中所有距离为 K 的结点

反转，把子节点指向父节点。

class Solution {
public:
    vector<int> res;
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        TreeNode *dummy=new TreeNode(-1);
        dummy->left=target->left;
        rev(root,target,NULL);
        
        dfs(target,K);
        if(K)dfs(dummy,K);
        return res;
    }
    
    // 从target开始，儿子反向指父亲
    bool rev(TreeNode *root,TreeNode *target,TreeNode * fa){
        if(!root)return false;
        
        if(root==target){
            root->left=fa;
            return true;
        }
        
        if(rev(root->left,target,root)){
            root->left=fa;
            return true;
        }
        if(rev(root->right,target,root)){
            root->right=fa;
            return true;
        }
        
        return false;
    }
    
    void dfs(TreeNode *root,int k){
        if(!root)return ;
        if(k==0){
            res.push_back(root->val);
            return ;
        }
        dfs(root->left,k-1);
        dfs(root->right,k-1);
    }
    
};