938. Range Sum of BST - Easy

前往題目

想法

• 走訪所有節點時判斷並加入結果

思路

遞迴

1. 除了遇到null節點，其餘都判斷其值是否在範圍內，是的話就更新結果
2. 呼叫兩次方法，並傳入左子節點和右子節點

Code

class Solution {
    int res = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;

        if (root.val >= low && root.val <= high) {
            res += root.val;
        }

        rangeSumBST(root.left, low, high);
        rangeSumBST(root.right, low, high);

        return res;
    }

}

不用額外全局變數的寫法

public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }

        int currentVal = (root.val >= low && root.val <= high) ? root.val : 0;

        int leftSum = rangeSumBST(root.left, low, high);
        int rightSum = rangeSumBST(root.right, low, high);

        return currentVal + leftSum + rightSum;
    }
}