二叉查找树中搜索区间

LeetCode题目地址

递归法

 def searchInTree(self, root, k1, k2):
        if root == None:
            return
        if root.val > k2:
            self.searchInTree(root.left,k1,k2)
        elif root.val < k1:
            self.searchInTree(root.right,k1,k2)
        else:
            self.result.append(root.val)
            self.searchInTree(root.left,k1,k2)
            self.searchInTree(root.right,k1,k2)
        
    def searchRange(self, root, k1, k2):
        # write your code here
        if k1 > k2:
            return []
        self.result = []
        self.searchInTree(root,k1,k2)
        return sorted(self.result)

层次遍历法

# write your code here
        if k1 > k2 or root == None:
            return []
        
        result = []
        queue = [root]
        size = 0
        while len(queue) != 0:
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                if node == None:
                    continue
                if node.val < k1:
                    #无需遍历所有点，提前砍掉不符合的分支
                    queue.append(node.right)
                elif node.val > k2:
                    queue.append(node.left)
                else:
                    result.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
        return sorted(result)