这是悦乐书的第359次更新,第386篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第221题(顺位题号是938)。给定二叉搜索树的根节点,返回节点值在[L,R]之间的所有节点的值的总和。二叉搜索树的节点值唯一。例如:

输入:root = [10,5,15,3,7,null,18],L = 7,R = 15
输出:32

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

注意:

  • 树中的节点数最多为10000。

  • 最终答案保证不到2^31。

02 第一种解法

既然给的是二叉搜索树,那么遍历节点我们就选取中序遍历的方式,这样最直接,存入List中,然后遍历List中的节点值,将节点值大于等于L且小于等于R的进行累加,最后返回sum即可。

/**
 * 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) {
        List<Integer> list = new ArrayList<Integer>();
        helper(root, list);
        int sum = 0;
        for (Integer num : list) {
            if (num >= L && num <= R) {
                sum += num;
            }
        }
        return sum;
    }

    public void helper(TreeNode root, List<Integer> list){
        if (root == null) {
            return ;
        }
        helper(root.left, list);
        list.add(root.val);
        helper(root.right, list);
    }
}


03 第二种解法

针对第一种解法,我们也可以使用迭代的方式来实现,借助

/**
 * 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) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem != null) {
                list.add(tem.val);
            }
            if (tem != null && tem.left != null) {
                stack.push(tem.left);
            }
            if (tem != null && tem.right != null) {
                stack.push(tem.right);
            }
        }
        int sum = 0;
        for (Integer num : list) {
            if (num >= L && num <= R) {
                sum += num;
            }
        }
        return sum;
    }
}


04 第三种解法

我们其实不用将节点值存起来后再统一处理,直接在遍历节点的时候,将在[L,R]范围内的节点值累加即可,最后返回sum。此解法是迭代的方式。

/**
 * 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) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem != null) {
                if (tem.val >= L && tem.val <= R) {
                    sum += tem.val;
                }
            }
            if (tem != null && tem.left != null) {
                stack.push(tem.left);
            }
            if (tem != null && tem.right != null) {
                stack.push(tem.right);
            }
        }
        return sum;
    }
}


05 第四种解法

针对第三种解法,我们也可以使用递归的方式。定义一个全局变量sum,依旧使用中序遍历的方式,将在[L,R]范围内的节点值累加,最后返回sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private Integer sum = 0;

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


06 第五种解法

针对第四种解法,我们也可以不使用全局变量,借助二叉搜索树节点值按照左根右的大小排列特性,如果当前节点值比L小,就往右边找,如果比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;
        }
        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);
    }
}


07 小结

算法专题目前已连续日更超过七个月,算法题文章227+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!