題目連結:
題目意譯:
給定一二元搜尋樹(Binary Search Tree)之根節(jié)點,回傳所有位於範圍 [low,high] 中的節(jié)點值之總和。
限制:
樹的節(jié)點數位於範圍 [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
解題思維:
一樣可以寫成遞迴形式,而且可以避免不必要計算之節(jié)點:
RangeSum(TreeNode *root)
如果 root 為空節(jié)點,回傳 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。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。