LeetCode（Tree)938. Range Sum of BST

野性酷女 2023-09-26 20:37 98阅读 0赞

# 1.问题 #

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range \[low, high\].

Example 1:  
![在这里插入图片描述][6e1f990148904c2ea60cae66109d576b.png]

> Input: root = \[10,5,15,3,7,null,18\], low = 7, high = 15  
> Output: 32  
> Explanation: Nodes 7, 10, and 15 are in the range \[7, 15\]. 7 + 10 + 15 = 32.

Example 2:  
![在这里插入图片描述][475a305800da46f5944803ab55a2a785.png]

> Input: root = \[10,5,15,3,7,13,18,1,null,6\], low = 6, high = 10  
> Output: 23  
> Explanation: Nodes 6, 7, and 10 are in the range \[6, 10\]. 6 + 7 + 10 = 23.

Constraints:

*  The number of nodes in the tree is in the range \[1, 2 \* 104\].
 *  1 <= Node.val <= 105
 *  1 <= low <= high <= 105
 *  All Node.val are unique.

# 2. 解题思路 #

## 方法1： ##

> 1.递归的过程中，我们首先判断当前节点是否为空，如果为空则返回0  
> 2. 否则判断当前节点的值是否在指定的范围内，如果是则将其值加到sum中，然后分别递归遍历左子树和右子树  
> 3. 将遍历结果相加并返回。

## 方法2： ##

> 对于二叉搜索树，由于其特殊的性质，我们可以采用一种类似于深度优先搜索的算法来遍历整个树，同时在遍历的过程中根据节点的值和给定的范围来判断节点是否需要计入和中。
> 
> 1.  初始化一个存储节点的栈，并将根节点入栈。
> 2.  循环处理栈中所有节点，对于每个节点进行如下处理：
> 3.  如果节点的值在给定范围内，则将其值加到和中。
> 4.  如果节点的值大于下限，则将其左子节点入栈。
> 5.  如果节点的值小于上限，则将其右子节点入栈。
> 6.  最后返回符合条件的节点值的和。
> 
> 值得注意的是，在这个过程中，由于二叉搜索树的特殊性质，我们可以在遍历过程中通过比较节点值和范围的大小来判断是否需要遍历节点的左子树或右子树，从而实现了对整个树的快速遍历。

# 3. 代码 #

## 代码1： ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public int rangeSumBST(TreeNode root, int low, int high) {
        
            if (root == null) {
         // 如果当前节点为空，返回0
                return 0;
            }
            int sum = 0; // 定义一个变量sum来记录符合条件的节点值的和
            if (root.val >= low && root.val <= high) {
         // 如果当前节点的值在指定的范围内，将其值加到sum中
                sum += root.val;
            }
            if (root.val > low) {
         // 如果当前节点的值大于下限，递归遍历左子树，并将遍历结果累加到sum中
                sum += rangeSumBST(root.left, low, high);
            }
            if (root.val < high) {
         // 如果当前节点的值小于上限，递归遍历右子树，并将遍历结果累加到sum中
                sum += rangeSumBST(root.right, low, high);
            }
            return sum; // 返回符合条件的节点值的和
        }
    }

> 解题思路基本相同

class Solution {
        
        public int rangeSumBST(TreeNode root, int low, int high) {
        
            if (root == null) return 0; // 如果当前节点为空，返回0
            if (root.val <= low) {
         // 如果当前节点的值小于下限，递归遍历右子树，并将遍历结果与当前节点的值（如果等于下限则加上）相加
                return rangeSumBST(root.right, low, high) + (root.val == low ? root.val : 0);
            }
            if (root.val >= high) {
         // 如果当前节点的值大于上限，递归遍历左子树，并将遍历结果与当前节点的值（如果等于上限则加上）相加
                return rangeSumBST(root.left, low, high) + (root.val == high ? root.val : 0);
            }
            return rangeSumBST(root.left, low, high) + root.val + rangeSumBST(root.right, low, high); // 如果当前节点的值在指定范围内，递归遍历左子树、当前节点和右子树，并将遍历结果相加
        }
    }

## 代码2： ##

class Solution {
        
        public int rangeSumBST(TreeNode root, int low, int high) {
        
            // 创建一个存储节点的栈
            Stack<TreeNode> stack = new Stack<>();
            // 初始化节点值的和为0
            int sum = 0;
            // 将根节点入栈
            stack.push(root);
            // 循环处理栈中所有节点
            while (!stack.empty()) {
        
                // 取出栈顶的节点
                TreeNode node = stack.pop();
                if (node != null) {
        
                    // 如果节点值在给定范围内，则将其值加到和中
                    if (low <= node.val && node.val <= high) {
        
                        sum += node.val;
                    }
                    // 如果节点值大于下限，则将其左子节点入栈
                    if (low < node.val) {
        
                        stack.push(node.left);
                    }
                    // 如果节点值小于上限，则将其右子节点入栈
                    if (node.val < high) {
        
                        stack.push(node.right);
                    }
                }
            }
            // 返回符合条件的节点值的和
            return sum;
        }
    }

[6e1f990148904c2ea60cae66109d576b.png]: https://img-blog.csdnimg.cn/6e1f990148904c2ea60cae66109d576b.png
[475a305800da46f5944803ab55a2a785.png]: https://img-blog.csdnimg.cn/475a305800da46f5944803ab55a2a785.png