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

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

更新於 發佈於 閱讀時間約 4 分鐘

題目敘述

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

題目的原文敘述


測試範例

Example 1:

raw-image
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:

raw-image
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

avatar-img
小松鼠的演算法樂園
95會員
426內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。