938. 二叉搜索树的范围和

不念不忘少年蓝@ 2023-02-18 03:02 15阅读 0赞

# 题目来源 #

[LEETCODE][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
    输出：32 = 10 + 7 + 15
    
    
    输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
    输出：23 = 10 + 7 + 6

# 题目解析 #

## 使用栈遍历所有值 ##

*  初始化一个栈用来遍历二叉树，初始化一个链表用来存储符合条件的值，然后求和
 *  本质是一个前序遍历

class Solution {
        
        public int rangeSumBST(TreeNode root, int L, int R) {
        
            if (root == null){
        
                return 0;
            }
    
            int ans = 0;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()){
        
                TreeNode top = stack.pop();
                if (top.val >= L && top.val <= R){
        
                    ans = ans + top.val;
                }
    
                if (top.right != null){
        
                    stack.push(top.right);
                }
                if (top.left != null){
        
                    stack.push(top.left);
                }
            }
    
            return ans;
        }
    }

![在这里插入图片描述][20200615153201624.png]

剪枝

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int rangeSumBST(TreeNode root, int L, int R) {
        
                  if (root == null){
        
                return 0;
            }
    
            int ans = 0;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()){
        
                TreeNode top = stack.pop();
                if (top.val >= L && top.val <= R){
        
                    ans = ans + top.val;
                    if (top.left != null){
        
                        stack.push(top.left);
                    }
    
                    if (top.right != null){
        
                        stack.push(top.right);
                    }
                }else if (top.val < L){
        
                    if (top.right != null){
        
                        stack.push(top.right);
                    }
                }else {
        
                    if (top.left != null){
        
                        stack.push(top.left);
                    }
                }
    
            }
    
            return ans;
        }
    }

![在这里插入图片描述][20200615160339147.png]

# 使用递归： #

不剪枝

class Solution {
        
        public int rangeSumBST(TreeNode root, int L, int R) {
        
                    if (root == null){
        
                return 0;
            }
    
            int ans = 0;
            ans = ans + rangeSumBST(root.left, L, R); // 一直递归到最下面的那个节点
            ans = ans + rangeSumBST(root.right, L, R);
            if (root.val >= L && root.val <= R){
        
                ans = ans + root.val;
            }
    
            return ans;
        }
    }

![在这里插入图片描述][20200615154710970.png]  
如果当前节点值小于L，说明其左子树所有节点均小于L，可以将左子树剪去；  
如果当前节点值大于R，说明其右子树所有节点均大于R，可以将右子树剪去；  
否则，可以将其值累加上，并且分别对左右节点递归函数即可。即：当前节点值 + 左子树 + 右子树

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int rangeSumBST(TreeNode root, int L, int R) {
        
            if (root == null){
        
                return 0;
            }
    
            int ans = 0;
            if (root.val < L){
        
                return rangeSumBST(root.right, L, R);
            }
            if (root.val > R){
        
                return rangeSumBST(root.left, L, R);
            }
    
    
        //当前节点再两数之间，把自身值加到结果里取，并往左右子节点递归
            return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
        }
    }

![在这里插入图片描述][20200615155831580.png]

[LEETCODE]: https://leetcode-cn.com/problems/range-sum-of-bst/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615160348808.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200615153201624.png]: https://img-blog.csdnimg.cn/20200615153201624.png
[20200615160339147.png]: https://img-blog.csdnimg.cn/20200615160339147.png
[20200615154710970.png]: https://img-blog.csdnimg.cn/20200615154710970.png
[20200615155831580.png]: https://img-blog.csdnimg.cn/20200615155831580.png