LeetCode 938. 二叉搜索树的范围和（二叉树遍历+搜索剪枝）

示例 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。

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);
    	}
    }
};

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;
    }
};