LeetCode 938. 二叉搜索树的范围和（二叉树遍历+搜索剪枝）_搜索在给定范围的键二叉树

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。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

来源：力扣（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);
    	}
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

中序遍历循环+剪枝

• 中序是递增序列，当当前值大于R时，后面均大于R，break

运行时间比较长，可能减的枝子没有递归多，递归枝杈比较多，随着深度变大，很大程度可被减掉

class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        int sum = 0;
        stack<TreeNode*> 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)//中序非降，后面都大于R
        		break;
        	root = root->right;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23