代码随想录算法训练营第十七天| 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

513.找树左下角的值

public int findBottomLeftValue(TreeNode root) {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    Boolean[] flag = new Boolean[1];
    flag[0] = true;
    dfs(root, path, ans, flag);

    int maxSizeIndex = 0;
    if (ans.size() == 0) {
        return -1;
    }
    int maxSize = ans.get(0).size();
    for (int i = 0; i < ans.size(); i++) {
        if (maxSize < ans.get(i).size()) {
            maxSize = ans.get(i).size();
            maxSizeIndex = i;
        }
    }
    if (ans.get(maxSizeIndex).size() == 0) {
        return -1;
    }

    return ans.get(maxSizeIndex).get(ans.get(maxSizeIndex).size() - 1);
}

public void dfs(TreeNode root, List<Integer> path, List<List<Integer>> ans, Boolean[] flag) {
    if (root == null) {
        return;
    }
    path.add(root.val);
    if (root.left == null && root.right == null) {
        ans.add(new ArrayList<Integer>(path));
    }
    // flag[0] = true;
    dfs(root.left, path, ans, flag);
    // flag[0] = false;
    dfs(root.right, path, ans, flag);
    path.remove(path.size() - 1);

}

112. 路径总和

public boolean hasPathSum(TreeNode root, int targetSum) {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    dfs(root, path, ans);
    for (List<Integer> an : ans) {
        int sum = 0;
        for (Integer integer : an) {
            sum += integer;
        }
        if (sum == targetSum) {
            return true;
        }
    }
    return false;
}

public void dfs(TreeNode root, List<Integer> path, List<List<Integer>> ans) {
    if (root == null) {
        return;
    }
    path.add(root.val);
    if (root.left == null && root.right == null) {
        ans.add(new ArrayList<Integer>(path));
    }
    dfs(root.left, path, ans);
    dfs(root.right, path, ans);
    path.remove(path.size() - 1);

}

105.从前序与中序遍历序列构造二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, map);
}

public TreeNode build(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> inMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }

    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);

    Integer rootIndex = inMap.get(rootVal);
    //左子树的长度
    int instance = rootIndex - inStart;
????//左递归,分解成子问题,每次递归去除根节点,保留左子树的节点??
    root.left = build(preorder, inorder, preStart + 1, preStart + instance, inStart, inStart + instance - 1, inMap);
?   //右递归,分解成子问题,每次递归去除根节点,保留右子树的节点??
    root.right = build(preorder, inorder, preStart + instance + 1, preEnd, inStart + instance + 1, inEnd, inMap);

    return root;
}