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

发表于 | 分类于
愉快的周末从ac 开始 （并没有

用时： 60 min

思路还是很简单的，先用 DFS 给每一个节点加上 parent ，顺便找到需要的target 。

然后从 target 出发，用DFS找到离target距离为K 的点 。

依次找到target的所有父级，用 DFS 找到距离为 K 的点。

花费时间比较多的原因是，找到父级后，又用 DFS 原路找了回来，造成了内存溢出。

避免的方法是找到父级后，如果自身是左孩子，就去右孩子找（因为左孩子已经找过了），反之则反

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var distanceK = function(root, target, K) {
    var node = null
    var res = []
    var dfs = function (root) {
        if (root === target) {
            node = root
        }
        if (root.left) {
            root.left.parent = root
            dfs(root.left)
        }
        if (root.right) {
            root.right.parent = root
            dfs(root.right)
        }
    }
    dfs(root)
    var search = function (root,index) {
        if (!root) return 
        if (index === K) {
            res.push(root.val)
        }
        root.left && search(root.left,index + 1)
        root.right &&  search(root.right,index + 1)
    }
    search(node,0)
    var index = 1
    // 父节点离node 的初始距离是 1
    while(index <= K && node.parent) {
        if(index === K) {
            res.push(node.parent.val)
            break
        } 
        if (node.parent.left === node) {
            search(node.parent.right,++index)
        } else {
            search(node.parent.left,++index)
        }
        node = node.parent  
    }
    return res
};

需要注意的几个点

  1. 注意判空
  2. 父节点本身可能就是需要找到的节点，如果父节点本身就是距离k，就没必要继续找下去了。