路徑總和-112

題目描述

給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum 。判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等於目標和 targetSum 。如果存在，返回 true ；否則，返回 false 。
葉子節點 是指沒有子節點的節點。

解題思路

我們這題採用任何一種遍歷方式都是可以的，這題同樣是有回溯的思想，如果不太懂的話可以去看看前面《求二叉樹的左右路徑》這一題，我們先去遍歷左子樹，遍歷的時候如果節點的左右子樹都為空說明我們已經到了葉子節點，此時我們就可以做判斷了，看看是不是和我們的targetSum一致，如果不一致則它的父節點會產生回溯去遍歷父節點的另一個子樹，同樣再去看看是否和targetSum是否一致，如果一致就可以直接填寫結果，不一致則繼續由它們的父節點回溯去判斷另一顆子樹。

代碼實例

class Solution {
    public boolean judge = false;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return false;
        }else{
            list.add(root.val);
            bianli(root, targetSum, list);
            return judge;
        }

    }

    public void bianli(TreeNode root, int targetSum, List<Integer> list) {
        if (root.left == null && root.right == null) {
            if (sum(list) == targetSum) {
                judge = true;
                return;
            }
        }
        
        if (root.left != null) {
            list.add(root.left.val);
            bianli(root.left, targetSum, list);
            list.remove(list.size() - 1);
        }

        if (root.right != null) {
            list.add(root.right.val);
            bianli(root.right, targetSum, list);
            list.remove(list.size() - 1);

        }

    }

    public int sum(List<Integer> list) {
        int sum = 0;
        for (Integer in : list) {
            sum += in;
        }
        return sum;
    }

}