• API
• FAQ
• Tools
• Archive
SHARE
TWEET # 1506. All Nodes Distance K in Binary Tree goodwish  Oct 23rd, 2019 132 in 157 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. O(n). 模拟类型, 按照题目逻辑, 硬算, 主要用到递归查找.
2. 处理逻辑:
3. loop each node in (root to target) path, find child from node with (k - parent_level) distance.
4. parent_level: node 距离 target 的层数.
5.
6. 封装两个辅助函数.
7. 1. log_path(root, target, path, res): find target, log path from root to target, include target.
8. 2. find_child(m, node, used, res): find m level child from root.
9. .
10.
11. class Solution:
12.     """
13.    @param root: the root of the tree
14.    @param target: the target
15.    @param K: the given K
16.    @return: All Nodes Distance K in Binary Tree
17.    """
18.     def distanceK(self, root, target, K):
19.         # 模拟类型, 按照题目逻辑, 硬算.
20.         # find target, log path
21.         # find child from parent with k - parent_level
22.         res = []
23.         self.dfs(root, target, [], res)
24.         path = res
25.         dep = len(path)
26.         used = set(path)
27.         k = K
28.         path.reverse()
29.         end = dep if dep <= k + 1 else k + 1
30.         res = []
31.         for i, node in enumerate(path[:end]):
32.             used.remove(node)
33.             self.dfs_k(node, used, k - i, res)
35.         return res
36.
37.     def dfs_k(self, root, used, k, res):
38.         if not root:
39.             return
40.         if root in used:
41.             return
42.         if k == 0:
43.             res.append(root.val)
44.             return
45.         self.dfs_k(root.left, used, k - 1, res)
46.         self.dfs_k(root.right, used, k - 1, res)
47.
48.
49.     def dfs(self, root, target, path, res):
50.         if not root:
51.             return
52.         if res:
53.             return
54.         if root == target:
55.             res.append(path + [root])
56.             return
57.         path.append(root)
58.         self.dfs(root.left, target, path, res)
59.         self.dfs(root.right, target, path, res)
60.         path.pop()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?