經典圖論題 二元搜索樹的區間和 Range Sum of BST_Leetcode #938

Todd Quackenbush on Unsplash

題目敘述

題目會給定我們一顆二元搜索樹BST的根結點，
還有一個指定區間的上邊界R 和 下邊界L。
請問二元搜索樹中，所有落在指定區間內的節點元素值的總和是多少?

題目的原文敘述

測試範例

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 2 * 10^4].
• 1 <= Node.val <= 10^5
• 1 <= low <= high <= 10^5
• All Node.val are unique.

演算法

善加利用BST的先天定義與特質:

BST本身是一個排序好的二元樹。

左子樹一定比根節點的值還小。

右子樹一定比根結點的值還大。

題目已經給了區間的上邊界R 和 下邊界L，我們只要依照節點元素值的大小去做判斷，落在區間內的元素做加總，再回傳答案即可。

程式碼

class Solution:
            
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        
        if root is None:
            # empty node or empty tree
            return 0
        
        
        # Divide and conquer with pruning redundant cases
        if root.val < L:
            # root is smaller than lower bound L, only consider and traverse right sub-tree
            return self.rangeSumBST( root.right, L, R )
        
        elif root.val > R:
            # root is larger than upper bound R, only consider and traverse left sub-tree
            return self.rangeSumBST( root.left, L, R )

        else:
            # root is in range, traverse both left and right sub-trees
            return root.val + self.rangeSumBST( root.right, L, R ) + self.rangeSumBST( root.left, L, R )

關鍵知識點

記得聯想到BST二元搜索樹的先天定義與特質:

BST本身是一個排序好的二元樹。

左子樹一定比根節點的值還小。

右子樹一定比根結點的值還大。

題目的定義，往往就暗藏解題的線索唷!

複雜度分析

時間複雜度:

O(n) DFS拜訪整張圖，每個節點至多拜訪一次，O(n)。

空間複雜度:

O(n) DFS拜訪整張圖，最大深度發生在整棵樹向左歪斜或者向右歪斜時 = O(n)。

Reference:

[1] Python O( n ) sol. based on divide-and-conquer with pruning, 85%+ - Range Sum of BST - LeetCode