原題
給定兩個(gè)值 k1 和 k2（k1 < k2）和一個(gè)二叉查找樹的根節(jié)點(diǎn)铭腕。找到樹中所有值在 k1 到 k2 范圍內(nèi)的節(jié)點(diǎn)。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找樹的中的節(jié)點(diǎn)值啄糙。返回所有升序的節(jié)點(diǎn)值。
如果有 k1 = 10 和 k2 = 22, 你的程序應(yīng)該返回 [12, 20, 22].
20
/ \
8 22
/ \
4 12
解題思路
- 方法一：暴力解法，DFS遍歷所有節(jié)點(diǎn)绊率，符合要求的加入result中垂睬，最后result排序媳荒，返回
- 方法二：同樣是DFS遍歷，但加入判斷驹饺，相當(dāng)于剪枝钳枕。
- 如果
root.val > start則可以繼續(xù)左子樹 - 如果
root.val < end則可以繼續(xù)右子樹 - 如果
start <= root.val <= end則把root.val加入result
完整代碼
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
# 方法一
class Solution:
"""
@param root: The root of the binary search tree.
@param k1 and k2: range k1 to k2.
@return: Return all keys that k1<=key<=k2 in ascending order.
"""
def searchRange(self, root, k1, k2):
res = []
self.dfs(root, k1, k2, res)
return sorted(res)
def dfs(self, root, start, end, result):
if root != None:
if root.val >= start and root.val <= end:
result.append(root.val)
self.dfs(root.left, start, end, result)
self.dfs(root.right, start, end, result)
# 方法二
class Solution:
"""
@param root: The root of the binary search tree.
@param k1 and k2: range k1 to k2.
@return: Return all keys that k1<=key<=k2 in ascending order.
"""
def searchRange(self, root, k1, k2):
res = []
self.dfs(root, k1, k2, res)
return sorted(res)
def dfs(self, root, start, end, result):
if root != None:
if root.val > start:
self.dfs(root.left, start, end, result)
if root.val >= start and root.val <= end:
result.append(root.val)
if root.val < end:
self.dfs(root.right, start, end, result)
