算法第十五天|二叉树

513. 找树左下角的值

    List<Integer> list = new ArrayList<>();// 层序遍历只存放最左边的一个

    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);
    }

因为层序遍历是从左到右放入列表中，那么只用放入头一个。取出最后一层的数据即可

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) { // 叶子节点
            return targetSum == sum;
        }

        // 当前节点不是根节点
        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) { // 叶子节点
            return targetSum == root.val;
        }
    
        return hasPathSum2(root.right, targetSum - root.val) || hasPathSum2(root.left, targetSum - root.val);
    }

从根节点到叶子节点的路径总和，意味着要从根节点算起。

寻找到叶子节点，返回叶子节点的结果。然后判断左子树和右子树的通路

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);
    }

因为最后要做回溯，所以是一个后序二叉树遍历