从小白开始刷算法 dfs篇 leetcode.938

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int[] res = new int[1];
        dfs(root, low, high, res);
        return res[0];
    }
    private void dfs(TreeNode root, int low, int high,int[] result){
        if (root == null) {
            return;
        }
        //判断当前节点的值是否在给定区间内，如果是，则将其值加到结果数组res中
        if (low <= root.val && root.val <= high) {
            result[0] += root.val;
        }
        //递归地调用dfs函数遍历当前节点的左子树
        if (null != root.left) {
            dfs(root.left, low, high, result);
        }
        //递归地调用dfs函数遍历当前节点的右子树
        if (null != root.right) {
            dfs(root.right, low, high, result);
        }
    }
}

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        //判断当前节点的值是否大于上界high，如果是，则递归调用rangeSumBST函数处理当前节点的左子树
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        //判断当前节点的值是否小于下界low，如果是，则递归调用rangeSumBST函数处理当前节点的右子树
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        //如果当前节点的值在给定区间[low, high]内，则将当前节点的值加到结果中，并同时递归处理当前节点的左子树和右子树
        return root.val + 
            rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}