前往
大廳
主題

LeetCode - 938. Range Sum of BST 解題心得

Not In My Back Yard | 2021-02-19 00:00:07 | 巴幣 0 | 人氣 379

題目連結:


題目意譯:
給定一二元搜尋樹(Binary Search Tree)之根節點,回傳所有位於範圍 [low,high] 中的節點值之總和。

限制:
樹的節點數位於範圍 [1, 2 × 10 ^ 4] 中。
1 ≦ Node.val ≦ 10 ^ 5
1 ≦ low ≦ high ≦ 10 ^ 5
所有 Node.val 之值相異。



範例測資:
範例 1:
輸入: root = [10,5,15,3,7,null,18], low = 7, high = 15
輸出: 32

範例 2:
輸入: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
輸出: 23


解題思維:
一樣可以寫成遞迴形式,而且可以避免不必要計算之節點:
RangeSum(TreeNode *root)
  如果 root 為空節點,回傳 0。
  
  令一變數 S = 0。
  如果 root->val > low,則 S += RangeSum(root->left)
  (當 root->val < low 時,左子樹只會有更小值,所以不用加)
  
  如果 root->val < high,則 S += RangeSum(root->right)
  (當 root->val > high 時,右子樹只會有更大值,所以不用加)
  
  如果 low ≦ root->val ≦ high ,則 S += root->val
  回傳 S。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作