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[0]
  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)
  34.             used.add(node)
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top