二叉树

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

考点：
递归 + 二叉树遍历 + 调整树根

** 思路：**

1 先对target做一次层次DFS ，将层次为k的节点加入vector
2 递归调整，将target 调整为新的树根，
3 在对target 做一次 层次为k的节点检查

将 target 递归调整为新的树根时，类似于 递归反转单链表，
但有个小区别，需要找一个NULL的指针作为next。

 // start 20:45  21:30～ 21:50
class Solution {
public:
    vector<int> result;
    void DFS(TreeNode* root, int k){
        if(!root || k < 0){
            return ;
        }
        if( k == 0) {
            result.push_back(root->val);
            return ;
        }
        DFS(root->left, k-1);
        DFS(root->right, k-1);
    }
    // return true 表示find it
    bool adjustRoot(TreeNode* root, TreeNode* target) {
        if(!root) {
            return false;
        }
        if(root == target) {
            // 清除target左右子树
            target->left = target->right = NULL;
            return true;
        }
        if (adjustRoot(root->left, target)) {
            // 像递归反转单链表一样，
            // 区别是：这里需要判断 root->left 节点的左右孩子哪个为 NULL, 因为不能丢掉它的另外一个孩子
            if(root->left->left == NULL) {
                root->left->left = root;
            } else {
                root->left->right = root;
            }
            root->left = NULL;
            return true;
        }
        if (adjustRoot(root->right, target)) {
             // 像递归反转单链表一样
             // 区别是：这里需要判断 root->right 节点的左右孩子哪个为 NULL, 因为不能丢掉它的另外一个孩子
            if(root->right->right == NULL){
                root->right->right = root; 
            } else {
                root->right->left = root;
            }
            root->right = NULL;
            return true;
        }
        return false;
    }
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        DFS(target, K);
        if(K > 0) {
            // 反转 root
            adjustRoot(root, target);
            DFS(target, K);     
        }
        return result;
    }
};