題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個二元樹 root 和一個整數 sum

回傳這棵樹有沒有一條路徑的所有節點總和為 sum

必須得要走到最後一個節點

解題思路

這題看是要寫個遞迴還是使用 Queue 搭配迴圈都可以

如果選擇遞迴版本的，可以用同一個方法來遞迴

每一層把 sum 減去節點的值後傳到下一層去

若遇到最後一個節點並且 sum 剛好為 0 就回傳 true

如果選擇迴圈版本，可以把上一層節點的值加到下一個節點中

若遇到最後一個節點並且值與 sum 一樣就回傳 true

程式碼

Java

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        
        int n = sum - root.val;
        
        if (root.left == null && root.right == null && n == 0) {
            return true;
        }
        
        return hasPathSum(root.left, n) || hasPathSum(root.right, n);
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            
            if (temp.left == null && temp.right == null && temp.val == sum) {
                return true;
            }
            
            if (temp.left != null) {
                temp.left.val += temp.val;
                queue.add(temp.left);
            }
            
            if (temp.right != null) {
                temp.right.val += temp.val;
                queue.add(temp.right);
            }
        }
        
        return false;
    }
}