GuilinDev

Lc0863

05 August 2008

863 All Nodes Distance K in Binary Tree

题目

We are given a binary tree (with root node 

1

root
), a 
1

target
node, and an integer value 
1

K
.

Return a list of the values of all nodes that have a distance 

1

K
from the 
1

target
node. The answer can be returned in any order.

  1. Example 1:
1
2
3
4
5
6
7
8
9
10
11
12

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.



Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

  1. The given tree is non-empty.
  2. Each node in the tree has unique values 
    1

    0 <= node.val <= 500
    .
  3. The 
    1

    target
    node is a node in the tree.
  4. 1

    0 <= K <= 1000
    .

分析

1) DFS - 对所有节点添加一个指向父节点的引用，之后做DFS，找到所有距离 

1

target
节点 
1

K
距离的节点。具体做法：

  • 先找到该节点，并记录父信息；
  • 除了路径上的父信息，其它无用删掉；
  • dfs, 中间利用父信息来避免重复遍历；

时间复杂度O(N)，空间复杂度O(N)

2) BFS，把树当作图来处理，从起始点BFS搜索路径长度为K的集合就好了，二叉树父节点到子节点好办，问题是子节点是没法回溯其父节点的，因此需要先建立左右子节点到父节点的关系，用哈希表保存。

时间复杂度O(N)，空间复杂度O(N)

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, TreeNode> parents = new HashMap<>(); // 记录父节点信息
        parents.put(root, null);
        
        findNode(root, target, parents); // 在寻找目标节点的过程中，记录父节点信息，左右子节点为key，父节点为value
        
        Map<TreeNode, TreeNode> pathParents = new HashMap<>();
        
        cleanNonPathParent(target, parents, pathParents);
        List<Integer> res = new ArrayList<>();
        dfs(target, K , pathParents, res);
        
        return res;
    }
    /* 找到目标节点，从跟到目标节点的路径上的节点同时需要保存父节点，哈希保存 */
    private boolean findNode(TreeNode node, TreeNode target, Map<TreeNode, TreeNode> parents) {
        if(node == null) { // base case1
            return false;
        }
        if(node == target) { // base case2
            return true;
        }
        if(node.left != null) {
            parents.put(node.left, node);
            if(findNode(node.left, target, parents)){
                return true;
            }
        }
        if(node.right != null ) {
            parents.put(node.right, node);
            return findNode(node.right, target, parents);
        }
        return false;
    }
    /* 找到root - > target 路径上的父节点信息 ，其它信息无用且会干扰后续dfs过程*/
    private void cleanNonPathParent(TreeNode target, Map<TreeNode, TreeNode> parents, Map<TreeNode, TreeNode> pathParents){
        while(target != null ){
            pathParents.put(target, parents.get(target));
            target = parents.get(target);
        }
    }
    
    /* dfs, 有路径父节点的还要往上查询 */
    private void dfs(TreeNode root, int k, Map<TreeNode, TreeNode> pathParents, List<Integer> res ){
        if( root == null ){
            return;
        }
        k--;
        if( k  < 0 ){
            res.add(root.val);
            return;
        }
        if(!pathParents.containsKey(root.left) && root.left != null){
            dfs(root.left, k, pathParents, res);
        }
        if(!pathParents.containsKey(root.right) && root.right != null){
            dfs(root.right, k, pathParents, res);
        }
        if(pathParents.containsKey(root) && pathParents.get(root) !=null){
            dfs(pathParents.get(root), k, pathParents, res);
        }
    }
}

BFS

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
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
    //key 是子节点 value 是父节点
    private HashMap<TreeNode, TreeNode> map = new HashMap<>();
    //key 是子节点 value是是否访问
    private HashMap<TreeNode, Boolean> visited = new HashMap<>();

    private LinkedList<Integer> result = new LinkedList<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        if(k == 0) {
            result.add(target.val);
            return result;
        }

        bfs(root, null);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(target);
        visited.put(target, true);

        int step = 0;
        while(!queue.isEmpty()){
            step++;
            int size = queue.size();
            for (int i = 0; i < size ; i++) {
                TreeNode temp = queue.poll();
                if (temp.left != null && !visited.get(temp.left)){
                    if(step == k) result.add(temp.left.val);
                    queue.add(temp.left);
                    visited.put(temp.left, true);
                }
                if (temp.right != null && !visited.get(temp.right)){
                    if(step == k) result.add(temp.right.val);
                    queue.add(temp.right);
                    visited.put(temp.right, true);
                }
                TreeNode parent = map.get(temp);
                if(parent != null && !visited.get(parent)){
                    if(step == k) result.add(parent.val);
                    queue.add(parent);
                    visited.put(parent, true);
                }
            }
            if(step == k) break;
        }
        return result;
    }

    private void bfs(TreeNode node, TreeNode parent) {
        if(node == null) return;
        visited.put(node, false);
        map.put(node, parent);
        bfs(node.left, node);
        bfs(node.right, node);
    }
}
This site is open source. Improve this page.