现在用什么工具建网站,门户网站和社交网络的区别,瓜子二手车直卖网,有名的室内设计公司文章目录1. 题目2. 解题递归剪枝中序遍历循环剪枝1. 题目
给定二叉搜索树的根结点 root#xff0c;返回 L 和 R#xff08;含#xff09;之间的所有结点的值的和。 题目的意思#xff0c;节点的值在[L, R]这个区间内#xff0c;就加到结果里#xff0c;求所有符合条件的…
文章目录1. 题目2. 解题递归剪枝中序遍历循环剪枝1. 题目
给定二叉搜索树的根结点 root返回 L 和 R含之间的所有结点的值的和。 题目的意思节点的值在[L, R]这个区间内就加到结果里求所有符合条件的节点值加和
示例 1输入root [10,5,15,3,7,null,18], L 7, R 15
输出32
示例 2输入root [10,5,15,3,7,13,18,1,null,6], L 6, R 10
输出23提示树中的结点数量最多为 10000 个。
最终的答案保证小于 2^31。来源力扣LeetCode 链接https://leetcode-cn.com/problems/range-sum-of-bst 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
递归剪枝
二叉搜索树具有左子树所有值小于根节点右子树大于根节点根据以上性质注意递归法的剪枝 class Solution {
public:int rangeSumBST(TreeNode* root, int L, int R) {int sum 0;sumLR(root,L,R,sum);return sum;}void sumLR(TreeNode* root,int L,int R,int sum){if(root NULL)return;if(root-val L root-val R){sum root-val;sumLR(root-left,L,R,sum);sumLR(root-right,L,R,sum);}else if(root-val L){//左子树都小于L砍了sumLR(root-right,L,R,sum);}else if(root-val R){//右子树都大于R砍了sumLR(root-left,L,R,sum);}}
};中序遍历循环剪枝
中序是递增序列当当前值大于R时后面均大于Rbreak 运行时间比较长可能减的枝子没有递归多递归枝杈比较多随着深度变大很大程度可被减掉
class Solution {
public:int rangeSumBST(TreeNode* root, int L, int R) {int sum 0;stackTreeNode* stk;while(root || !stk.empty()){while(root){stk.push(root);root root-left;}root stk.top();stk.pop();if(root-val L root-val R)sum root-val;else if(root-val R)//中序非降后面都大于Rbreak;root root-right;}return sum;}
};
