112. Path Sum - Easy

前往題目

想法

• 走訪所有node，遇到leaf判斷當前總合是否等於目標總和

思路

遞迴

1. 遇到null回傳
2. 否則更新當前總和，如果不是leaf則繼續呼叫方法走訪左右子樹
3. 如果總和相等標記true

Code

class Solution {
    boolean res;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        res = false;
        find(root, 0, targetSum);
        return res;
    }

    private void find(TreeNode node, int curSum, int targetSum) {
        if (node == null) return;

        curSum += node.val;
        
        // Reached the leaf
        if (node.left == null && node.right == null) {
            if (curSum == targetSum)
                res = true;
            return;
        }

        find(node.left, curSum, targetSum);
        find(node.right, curSum, targetSum);
    }
}

不用額外的變數可以這樣寫

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return find(root, 0, targetSum);
    }

    private boolean find(TreeNode node, int curSum, int targetSum) {
        if (node == null) return false;

        curSum += node.val;

        // Reached the leaf
        if (node.left == null && node.right == null) {
            if (curSum == targetSum) return true;
        }

        return find(node.left, curSum, targetSum) || find(node.right, curSum, targetSum);
    }
}