原題

給定兩個值 k1 和 k2（k1 < k2）和一個二叉查找樹的根節(jié)點。找到樹中所有值在 k1 到 k2 范圍內(nèi)的節(jié)點。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找樹的中的節(jié)點值。返回所有升序的節(jié)點值。

如果有 k1 = 10 和 k2 = 22, 你的程序應(yīng)該返回 [12, 20, 22].

    20
   /  \
  8   22
 / \
4   12

解題思路

• 方法一：暴力解法，DFS遍歷所有節(jié)點，符合要求的加入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)