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

题意：找出二叉树中所有距离为k的节点

思路：

1. 先跟遍历树，把每一个节点的parent节点找到，并计算他们到root的距离
2. 遍历target的子节点，查看，target到root的距离 － 子节点到root的距离是否为k
3. 遍历target的parent节点，对于每一个parent的节点，查看，target到root的距离 － parent到root的距离是否为k
4. 遍历parent的非target的子树节点，查看，子树节点到root的距离－parent到root的距离＋target到root的距离－parent到root的距离是否为k
5. 返回结果

思想：树的先跟遍历

复杂度：时间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;
        }
    }
}