題目敘述
題目會給定我們一顆二元搜索樹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^51 <= low <= high <= 10^5- All
Node.valare 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
