513. 找樹左下角的值

    List<Integer> list = new ArrayList<>();// 層序遍歷只存放最左邊的一個(gè)

    public int findBottomLeftValue(TreeNode root) {

        getValueByLevel(root, 0);
        return list.get(list.size() - 1);
    }

    private void getValueByLevel(TreeNode root, int deep) {
        if (root == null) {
            return;
        }
        if (list.size() == deep) {
            list.add(root.val);
        }
        getValueByLevel(root.left, deep + 1);
        getValueByLevel(root.right, deep + 1);
    }

因?yàn)閷有虮闅v是從左到右放入列表中，那么只用放入頭一個(gè)。取出最后一層的數(shù)據(jù)即可

112. 路徑總和

    public boolean hasPathSum(TreeNode root, int targetSum) {
        return pathSum(root, 0, targetSum);
    }

    private Boolean pathSum(TreeNode root, int sum, int targetSum) {
        if (root == null) {
            return false;
        }

        sum = sum + root.val;
        if (root.left == null && root.right == null) { // 葉子節(jié)點(diǎn)
            return targetSum == sum;
        }

        // 當(dāng)前節(jié)點(diǎn)不是根節(jié)點(diǎn)
        Boolean left = pathSum(root.left, sum, targetSum);  //左子樹是否能找到
        Boolean right = pathSum(root.right, sum, targetSum);  //右子樹是否能找到
        return left || right;
    }


    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
    
        if (root.left == null && root.right == null) { // 葉子節(jié)點(diǎn)
            return targetSum == root.val;
        }
    
        return hasPathSum2(root.right, targetSum - root.val) || hasPathSum2(root.left, targetSum - root.val);
    }

從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑總和，意味著要從根節(jié)點(diǎn)算起。

尋找到葉子節(jié)點(diǎn)，返回葉子節(jié)點(diǎn)的結(jié)果。然后判斷左子樹和右子樹的通路

113. 路徑總和 II

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        getPath(root, new ArrayList<>(), targetSum);
        return list;
    }

    private void getPath(TreeNode root, ArrayList<Integer> value, int targetSum) {
        if (root == null) {
            return;
        }

        value.add(root.val);

        getPath(root.left, value, targetSum - root.val);
        getPath(root.right, value, targetSum - root.val);

        if (root.left == null && root.right == null) {
            if (targetSum == root.val) {
                list.add(new ArrayList<>(value));
            }
        }

        // 回溯
        targetSum += value.get(value.size() - 1);
        value.remove(value.size() - 1);
    }

因?yàn)樽詈笠龌厮?，所以是一個(gè)后序二叉樹遍歷