Leetcode 938. Range Sum of BST(树)


题目来源:https://leetcode.com/problems/reorder-log-files/description/

标记难度:Medium

提交次数:1/1

代码效率:

  • 剪枝:120ms
  • 不剪枝:120ms

题意

给定一棵二叉查找树、LR,返回[L, R]中的结点的值的和。

分析

这个题总的来说很简单。直接DFS,然后根据当前node的值进行剪枝即可。(事实上不剪枝也能过,而且没慢多少。)

代码

不剪枝

1
2
3
4
5
6
7
8
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
if (root == NULL) return 0;
return rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R) +
(L <= root->val && root->val <= R ? root->val : 0);
}
};

剪枝

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
if (root == NULL) return 0;
int sum = 0;
if (root->val > L) sum += rangeSumBST(root->left, L, R);
if (root->val < R) sum += rangeSumBST(root->right, L, R);
return sum + (L <= root->val && root->val <= R ? root->val : 0);
}
};

 评论