938. Range Sum of BST

Although this is an easy question, but it is prone to bugs, and the code can be better.

Following is my first solution, didn't use the feature of BST.

private int sum =0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root==null)
            return sum;
        if(root.val>=low&&root.val<=high){
            sum+=root.val;
        }
        rangeSumBST(root.left, low, high);    //whether root.val is in the range or not, this line should be executed, think about why
        rangeSumBST(root.right, low, high);   //whether root.val is in the range or not, this line should be executed, think about why
return sum; }

The following solution use the feature of BST, reduced unnecessary implementations:

    private int sum =0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root==null)
            return sum;
        if(root.val>high)
            rangeSumBST(root.left, low, high);
        else if(root.val<low)
            rangeSumBST(root.right, low, high);
        else{
            sum+=root.val;
            rangeSumBST(root.left, low, high);
            rangeSumBST(root.right, low, high);
        }
        return sum;
    }

The sum in above solution can be removed:

    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null)
            return 0;
        if (root.val > high)
            return rangeSumBST(root.left, low, high);
        else if (root.val < low)
            return rangeSumBST(root.right, low, high);
        else {
            return rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + root.val;
        }
    }

 

上一篇:Lintcode 1872 · Minimum Cost to Connect Sticks [Python]


下一篇:OAF_开发系列13_实现OAF通过Vector动态查询设置(案例)