jinhuang1102

272. Closest Binary Search Tree Value II

Mar 17th, 2019
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.31 KB | None | 0 0
  1. """
  2. Approach #1: 利用中序遍历将BST转化成有序数组。 之后我们再在有序数组中需要和目标值最近的k个值
  3. """
  4. class Solution(object):
  5.     def inorder(self, root, ls):
  6.         st = []
  7.         while st or root:
  8.             if root:
  9.                 st.append(root)
  10.                 root = root.left
  11.             else:
  12.                 root = st.pop()
  13.                 ls.append(root.val)
  14.                 root = root.right
  15.                
  16.    
  17.     def closestKValues(self, root, target, k):
  18.         """
  19.        :type root: TreeNode
  20.        :type target: float
  21.        :type k: int
  22.        :rtype: List[int]
  23.        """        
  24.         if k == 0:
  25.             return []
  26.        
  27.         ls = []
  28.         self.inorder(root, ls) # 用中序遍历将所有的节点值存到一个一位数组。由于binary search tree的性质,这个数组是有序的
  29.        
  30.         diff = sys.maxsize
  31.         idx = 0
  32.         for i in range(0, len(ls)):        # 之后遍历数组找到最近接target value的位置
  33.             if abs(target - ls[i]) <= diff:
  34.                 diff = abs(target - ls[i])
  35.                 idx = i
  36.                
  37.         left = idx - 1              # 找到后分别从当前位置的左和右开始向两端遍历
  38.         right = idx + 1
  39.        
  40.         res = []
  41.         for i in range(0, k):       # 需要遍历 k - 1 次,因为在开始遍历之前要先把当前的idx加入res中,这里需要考虑向两端遍历的边界条件
  42.             res.append(ls[idx])
  43.            
  44.             # 如果left 和 right 都没有超过边界,比较左右两边的值,然后将较差值的index 更新到 idx,之后再下一轮是把idx加入res
  45.             if left >= 0 and right <= len(ls) - 1:  
  46.                 if abs(ls[left] - target) > abs(ls[right] - target):
  47.                     idx = right
  48.                     right += 1
  49.                 else:
  50.                     idx = left
  51.                     left -= 1
  52.            
  53.             # 如果right已经超出边界,那么就只遍历left
  54.             elif left >= 0:
  55.                 idx = left
  56.                 left -= 1
  57.            
  58.             # 如果left已超出边界,那么就只遍历right
  59.             elif right < len(ls):
  60.                 idx = right
  61.                 right += 1
  62.                
  63.         return res
  64.  
  65.  
  66. """
  67. Approach #2: 思想是在inorder traversal过程中来找寻 k 个closest values。
  68.              其中涉及到另外一个topic,就是在array中寻找k个相近的值的方法
  69. """
  70. from collections import deque
  71.  
  72. class Solution:
  73.     def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
  74.         if k == 0:
  75.             return []
  76.        
  77.         queue = deque()
  78.        
  79.         st = []
  80.         while st or root:
  81.             if root:
  82.                 st.append(root)
  83.                 root = root.left
  84.             else:
  85.                 root = st.pop()
  86.                
  87.                 if len(queue) < k:
  88.                     queue.append(root.val)
  89.                 else:
  90.                     diff = abs(target - root.val)
  91.                     if diff < abs(target - queue[0]):
  92.                         queue.popleft()
  93.                         queue.append(root.val)
  94.                
  95.                 root = root.right
  96.        
  97.         return list(queue)
Advertisement
Add Comment
Please, Sign In to add comment