Re: [閒聊] 每日LeetCode
938. Range Sum of BST
https://leetcode.com/problems/range-sum-of-bst/description/
給定一個二元搜尋樹與兩個整數 low 與 high ，
傳回樹中所有值介於上下界之間的節點之總和。
--
思路：
二元搜尋樹的特性是任一個父節點的左子結點的值一定小於父結點的值，
右側子結點的值一定大於父結點的值，
所以相較於一般的走訪，
當碰到不在範圍內的節點時，
只要走訪其中一邊即可，
以遞迴的方式將節點的值與子樹的值相加後傳回，
而碰到空節點時就傳回0。
--
Python Code:
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) ->
int:
def dfs(node, l, h):
if node is None: return 0
if node.val > h: return dfs(node.left, l, h)
elif node.val < l: return dfs(node.right, l, h)
else: return node.val + dfs(node.left, l, h) + dfs(node.right, l,
h)
return dfs(root, low, high)
C++ Code:
class Solution {
private:
int dfs(TreeNode* node, int l, int h){
if (!node) return 0;
if (node->val < l) return dfs(node->right, l, h);
else if (node->val > h) return dfs(node->left, l, h);
else return node->val + dfs(node->left, l, h) + dfs(node->right, l, h)
;
}
public:
int rangeSumBST(TreeNode* root, int low, int high) {
return dfs(root, low, high);
}
};
--
咖啡是一種豆漿，
茶是一種蔬菜湯。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.84.252 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1704703157.A.7EC.html
推
01/08 16:40,
5月前
, 1F
01/08 16:40, 1F
推
01/08 16:40,
5月前
, 2F
01/08 16:40, 2F
討論串 (同標題文章)
完整討論串 (本文為第 595 之 719 篇)：
閒聊
1
3