Leetcode -863- All nodes with distance k in a binary tree

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

Given a binary tree (with root), a target node, and an integer value K.

Returns a list of values of all nodes with distance K from target. The answers can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], target = 5, K = 2 output:,4,1 [7] : for nodes with target distance (5) for the value of 2 nodes, value respectively, 4, 7 and 1Copy the code

​

Note that the input “root” and “target” are actually nodes in the tree. The above input is simply a serialized description of these objects.

Tip:

  1. The given tree is non-empty.
  2. Each node in the tree has a unique value0 <= node.val <= 500 。
  3. The target nodetargetIt’s a node in the tree.
  4. 0 <= K <= 1000.

Related Topics

  • The tree

  • Depth-first search

  • Breadth-first search

  • Binary tree

  • 👍 👎 0 342

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: DFS + hash

  • The idea is no problem at the beginning, the writing method is still some problems, consider the complex, rather than forward search, as reverse times
  • The easiest thing is to go through all the nodes and find the number of distances k
  • Find the relationship between the parent node and the child node, and then determine the distance by distance
Map<Integer, TreeNode> keyMap = new HashMap<>();
        List<Integer> res = new ArrayList<>();
​
        public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
            findKeyMap(root);
            dfs(target, 0.null, k);
            return res;
        }
​
        public void findKeyMap(TreeNode root) {
            if (root == null) {
                return;
            }
            if(root.left ! =null) {
                keyMap.put(root.left.val, root);
                findKeyMap(root.left);
            }
            if(root.right ! =null) { keyMap.put(root.right.val, root); findKeyMap(root.right); }}public void dfs(TreeNode target, int dis, TreeNode from, int k) {
            if (target == null) {
                return;
            }
            if (dis == k) {
                res.add(target.val);
            }
            if(target.left ! = from) { dfs(target.left, dis +1, target, k);
            }
            if(target.right ! = from) { dfs(target.right, dis +1, target, k);
            }
            if(keyMap.get(target.val) ! = from) { dfs(keyMap.get(target.val), dis +1, target, k); }}Copy the code

Time complexity

Idea 2: undirected graph + BFS

  • Three leaf is still strong

  • Define an undirected graph

  • The key here is the add function

  • The logic of BFS is to do BFS through a deque

  • Defines whether an access array record traverses the node

  • When k==0, it will look up the starting node

  • Insert into the result set

  • This kind of thinking requires a certain basis of data structure, which is hard for me to understand

  • If you need to find the diagram to build and search

  • Very good explanation by @Meteordream

  • What Sanye set up is an adjacencies list

  • The index of the array he is the node, and the value is an index IND

  • E [ind] corresponds to an edge

  • Ne [ind] indicates the index of the next join node

  • Let’s say I have nodes b, c that are connected to node A,

  • Ind1 = ind1; ind1 = ind1

  • E [ind1] = b shows that the first node connected to a is b

  • Then the index ind2 of the next node can be obtained by ne[ind1]

  • By e[ind2] = c, the second node connected to a is c

  • And then ne[ind2] = -1 means there’s no next node

  • The add function is kind of like a linked list header, assuming that node A already has a connected node B

  • So he[a]=ind, e[ind]=b

  • And then add a connected node C to A

  • Ne [new_ind] = he[a] = ind

  • Then create an edge e[new_ind] and update he[a] = new_ind

  • A -> b to a -> c -> b

  • You can think of it as he is the head of the adjacencies list, key is the node and val is a pointer to the head of a linked list that contains adjacent nodes

  • E is val, the adjacent node of the list node, and ne is next pointer of the list node

    int N = 1010, M = N * 2;
            int[] he = new int[N], e = new int[M], ne = new int[M];
            int idx;
            void add(int a, int b) {
                e[idx] = b;
                ne[idx] = he[a];
                he[a] = idx++;
            }
            boolean[] vis = new boolean[N];
            public List<Integer> distanceK(TreeNode root, TreeNode t, int k) {
                List<Integer> ans = new ArrayList<>();
                Arrays.fill(he, -1);
                dfs(root);
                Deque<Integer> d = new ArrayDeque<>();
                d.addLast(t.val);
                vis[t.val] = true;
                while(! d.isEmpty() && k >=0) {
                    int size = d.size();
                    while (size-- > 0) {
                        int poll = d.pollFirst();
                        if (k == 0) {
                            ans.add(poll);
                            continue;
                        }
                        for (inti = he[poll]; i ! = -1 ; i = ne[i]) {
                            int j = e[i];
                            if(! vis[j]) { d.addLast(j); vis[j] =true;
                            }
                        }
                    }
                    k--;
                }
                return ans;
            }
    ​
            private void dfs(TreeNode root){
                if (root == null) {return;
                }
                if(root.left! =null){
                    add(root.val,root.left.val);
                    add(root.left.val,root.val);
                    dfs(root.left);
                }
                if(root.right! =null){ add(root.val,root.right.val); add(root.right.val,root.val); dfs(root.right); }}Copy the code

Time complexity O(n)