Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Approach #1: 利用中序遍历将BST转化成有序数组。 之后我们再在有序数组中需要和目标值最近的k个值
- """
- class Solution(object):
- def inorder(self, root, ls):
- st = []
- while st or root:
- if root:
- st.append(root)
- root = root.left
- else:
- root = st.pop()
- ls.append(root.val)
- root = root.right
- def closestKValues(self, root, target, k):
- """
- :type root: TreeNode
- :type target: float
- :type k: int
- :rtype: List[int]
- """
- if k == 0:
- return []
- ls = []
- self.inorder(root, ls) # 用中序遍历将所有的节点值存到一个一位数组。由于binary search tree的性质,这个数组是有序的
- diff = sys.maxsize
- idx = 0
- for i in range(0, len(ls)): # 之后遍历数组找到最近接target value的位置
- if abs(target - ls[i]) <= diff:
- diff = abs(target - ls[i])
- idx = i
- left = idx - 1 # 找到后分别从当前位置的左和右开始向两端遍历
- right = idx + 1
- res = []
- for i in range(0, k): # 需要遍历 k - 1 次,因为在开始遍历之前要先把当前的idx加入res中,这里需要考虑向两端遍历的边界条件
- res.append(ls[idx])
- # 如果left 和 right 都没有超过边界,比较左右两边的值,然后将较差值的index 更新到 idx,之后再下一轮是把idx加入res
- if left >= 0 and right <= len(ls) - 1:
- if abs(ls[left] - target) > abs(ls[right] - target):
- idx = right
- right += 1
- else:
- idx = left
- left -= 1
- # 如果right已经超出边界,那么就只遍历left
- elif left >= 0:
- idx = left
- left -= 1
- # 如果left已超出边界,那么就只遍历right
- elif right < len(ls):
- idx = right
- right += 1
- return res
- """
- Approach #2: 思想是在inorder traversal过程中来找寻 k 个closest values。
- 其中涉及到另外一个topic,就是在array中寻找k个相近的值的方法
- """
- from collections import deque
- class Solution:
- def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
- if k == 0:
- return []
- queue = deque()
- st = []
- while st or root:
- if root:
- st.append(root)
- root = root.left
- else:
- root = st.pop()
- if len(queue) < k:
- queue.append(root.val)
- else:
- diff = abs(target - root.val)
- if diff < abs(target - queue[0]):
- queue.popleft()
- queue.append(root.val)
- root = root.right
- return list(queue)
Advertisement
Add Comment
Please, Sign In to add comment