12 Range Sum of BST

devi

发布于 2021-08-18 15:52:38

2760

题目

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15 Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 Output: 23

Note:

The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.

分析

题意：我没看明白…看看别人的说法吧

看完评论区吐槽回来… 题意：如例一[10,5,15,3,7,null,18],L=7，R=15，求出在[L,R]区间内的和，也就是10+15+7=32，所以很简单了，就是个遍历问题。

解答

/**
 * 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 res=0;
        int tmp=root.val;
        if(tmp>=L && tmp<=R)
            res+=tmp;
        return res + rangeSumBST(root.left,L,R) + rangeSumBST(root.right,L,R);
    }
}

运行状态不太理想，去看看大佬的解答。

下面这个是力扣中国官网给的递归算法

class Solution {
    int ans;
    public int rangeSumBST(TreeNode root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }

    public void dfs(TreeNode node, int L, int R) {
        if (node != null) {
            if (L <= node.val && node.val <= R)
                ans += node.val;
            if (L < node.val)
                dfs(node.left, L, R);
            if (node.val < R)
                dfs(node.right, L, R);
        }
    }
}

上述算法多了一步判断，如果node.val在[L,R]内才继续递归，这样就少了递归次数。

简化版的写法

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        return (L <= root.val && root.val <= R ? root.val : 0) + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R);
    }

利用栈实现迭代算法（注释在代码中）

class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
    	//初始化返回结果
        int ans = 0;
        //创建栈
        Stack<TreeNode> stack = new Stack();
        //将当前节点压入栈中
        stack.push(root);
        //如果栈非空，则循环
        while (!stack.isEmpty()) {
        	//创建一个节点接收栈中弹出的元素
            TreeNode node = stack.pop();
            //如果当前节点非空
            if (node != null) {
            	//如果当前节点在[L,R]之间
                if (L <= node.val && node.val <= R)
                	//累加至结果中
                    ans += node.val;
                //如果当前节点比L大，就将左子树根节点放入栈中
                if (L < node.val)
                    stack.push(node.left);
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        return ans;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/02/01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js