LeetCode 863. 二叉树中所有距离为 K 的结点（公共祖先/ DFS+BFS）

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1

注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
 
提示：
给定的树是非空的，且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.

class Solution {
    unordered_map<TreeNode*, int> pos;
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        vector<int> ans;
        dfs(root,0);
        int pt, pi, dis = 0;
        for(auto posi : pos)
        {
            pt = pos[target];
            pi = posi.second;
            dis = 0;
            while(pt != pi)
            {
                if(pt < pi)
                    pi = (pi-1)/2;
                else
                    pt = (pt-1)/2;
                dis++;
            }
            if(dis == K)
                ans.push_back(posi.first->val);
        }
        return ans;
    }
    void dfs(TreeNode* root, int p)
    {
        if(!root) return;
        pos[root] = p;
        dfs(root->left, 2*p+1);
        dfs(root->right, 2*p+2);
    }
};

class Solution {
    unordered_map<TreeNode*, TreeNode*> f;
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        dfs(root, NULL);
        vector<int> ans;
        unordered_set<TreeNode*> visited;
        queue<TreeNode*> q;
        q.push(target);
        visited.insert(target);
        int dis = 0, size;
        TreeNode* tp;
        while(!q.empty())
        {
            if(dis == K)
                break;
            size = q.size();
            while(size--)
            {
                tp = q.front();
                q.pop();
                if(tp->left && !visited.count(tp->left))
                {
                    q.push(tp->left);
                    visited.insert(tp->left);
                }
                if(tp->right && !visited.count(tp->right))
                {
                    q.push(tp->right);
                    visited.insert(tp->right);
                }
                if(f[tp] && !visited.count(f[tp]))
                {
                    q.push(f[tp]);
                    visited.insert(f[tp]);
                }
            }
            dis++;
        }
        while(!q.empty())
        {
            ans.push_back(q.front()->val);
            q.pop();
        }
        return ans;
    }
    void dfs(TreeNode* root, TreeNode* father)
    {
        if(!root) return;
        f[root] = father;//建立父节点连接
        dfs(root->left, root);
        dfs(root->right, root);
    }
};