題意：找出二叉樹中所有距離為k的節(jié)點(diǎn)

思路：

1. 先跟遍歷樹，把每一個節(jié)點(diǎn)的parent節(jié)點(diǎn)找到，并計算他們到root的距離
2. 遍歷target的子節(jié)點(diǎn)，查看，target到root的距離 － 子節(jié)點(diǎn)到root的距離是否為k
3. 遍歷target的parent節(jié)點(diǎn)，對于每一個parent的節(jié)點(diǎn)，查看，target到root的距離 － parent到root的距離是否為k
4. 遍歷parent的非target的子樹節(jié)點(diǎn)，查看，子樹節(jié)點(diǎn)到root的距離－parent到root的距離＋target到root的距離－parent到root的距離是否為k
5. 返回結(jié)果

思想：樹的先跟遍歷

復(fù)雜度：時間O（n)，空間O(n)

class Node {
    Node parent = null;
    int dis = 0;
    int dir = 0;
    TreeNode n = null;
    public Node(int dis, Node parent, int dir, TreeNode n) {
        this.dis = dis;
        this.parent = parent;
        this.dir = dir;
        this.n = n;
    }
}
class Solution {
    HashMap<TreeNode, Node> map = new HashMap();
    List<Integer> res = new ArrayList();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        build(root, 0, null, 0);
        int temp = map.get(target).dis;
        findInChild(target, temp, K);
        findParent(target, temp, K);
        return res;
    }
    
    void build(TreeNode root, int dis, Node pre, int dir) {
        if(root == null)
            return;
        Node cur = new Node(dis, pre, dir, root);
        map.put(root, cur);
        
        build(root.left, dis+1, cur, 1);
        build(root.right, dis+1, cur, 2);
    }
    
    void findInChild(TreeNode root, int total, int target) {
        if(root == null)
            return;
        int temp = map.get(root).dis;
        if(temp - total > target)
            return;
        if(temp - total == target) {
            res.add(root.val);
            return;
        }
        findInChild(root.left, total, target);
        findInChild(root.right, total, target);
    }
    
    void findParent(TreeNode root, int total, int target) {
        Node parent = map.get(root).parent;
        Node cur = map.get(root);
        while(parent != null) {
            int dis = parent.dis * 2 - total;
            if(total - parent.dis == target)
                res.add(parent.n.val);
            else {
                if(cur.dir == 1) {
                    findInChild(parent.n.right, dis, target);
                } else {
                    findInChild(parent.n.left, dis, target);
                }
            }
            cur = parent;
            parent = parent.parent;
        }
    }
}