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

前言
状态：513 用层序 AC、112AC（但时间复杂度较高））（解析中给的方法和想的不一样），113AC、106 不会
更新

1	24.06.07 初始记录

初步题解

513 找树左下角的值

题目链接：(https://leetcode.cn/problems/find-bottom-left-tree-value)

/**  
 * 看题目感觉层序遍历简单一点  
 * @param root 根节点  
 * @return 结果  
 */  
public int findBottomLeftValue(TreeNode root) {  
    List<List<Integer>> list = new ArrayList<>();  
    findBottomDFS(root, 0, list);  
    List<Integer> theLastLayer = list.get(list.size() - 1);  
    return theLastLayer.stream().filter(Objects::nonNull).collect(Collectors.toList()).get(0);  
}  
  
private void findBottomDFS(TreeNode root, int i, List<List<Integer>> list) {  
    if (root == null) {  
        return;  
    }  
  
    // 深度增加  
    i++;  
  
    if (list.size() < i) {  
        ArrayList<Integer> innerList = new ArrayList<>();  
        list.add(innerList);  
    }  
    list.get(i - 1).add(root.val);  
  
    findBottomDFS(root.left, i, list);  
    findBottomDFS(root.right, i, list);  
}

112 路径总和、113 路径总和 ii

题目链接：(https://leetcode.cn/problems/path-sum/description/)

/**  
 * 感觉之前做过求路径的题（递归+迭代）这题应该变换一下  
 * 时间复杂度好像有点高，剩下那题等看完解析后再写
 * 后面改用sum直接加减不遍历求总和，但是leetcode不通过，本地倒是测试没问题
 * @param root 根节点  
 * @param targetSum 目标和  
 * @return 结果  
 */  
public boolean hasPathSum(TreeNode root, int targetSum) {  
    if (root == null) {  
        return false;  
    }  
    List<Integer> list = new ArrayList<Integer>();  
    return hasPathSumBFS(root, list, targetSum);  
}  
  
private boolean hasPathSumBFS(TreeNode root, List<Integer> list, int targetSum) {  
    list.add(root.val);  
  
    if (root.left == null && root.right == null) {  
        // 求list中的总和  
        long sum = list.stream().collect(Collectors.summarizingInt(value -> value)).getSum();  
        return sum == targetSum;  
    }  
  
    boolean left = false;  
    boolean right = false;  
    if (root.left != null) {  
        left = hasPathSumBFS(root.left, list, targetSum);  
        list.remove(list.size() - 1);  
    }  
    if (root.right != null) {  
        right = hasPathSumBFS(root.right, list, targetSum);  
        list.remove(list.size() - 1);  
    }  
      
    return left || right;  
}

题目链接：(https://leetcode.cn/problems/path-sum-ii/)

public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {  
    List<Integer> list = new ArrayList<>();  
    List<List<Integer>> result = new ArrayList<>();  
    pathSumBFS(root, targetSum, result, list);  
    return result;  
}  
  
private static void pathSumBFS(TreeNode root, int targetSum, List<List<Integer>> result, List<Integer> list) {  
    if (root == null) {  
        return;  
    }  
  
    targetSum -= root.val;  
    list.add(root.val);  
  
    if (root.left == null && root.right == null) {  
        if (targetSum == 0) {  
            List<Integer> arrayList = new ArrayList<>(list);  
            result.add(arrayList);  
        }  
    }  
  
    if (root.left != null) {  
        pathSumBFS(root.left, targetSum, result, list);  
        list.remove(list.size() - 1);  
    }  
    if (root.right != null) {  
        pathSumBFS(root.right, targetSum, result, list);  
        list.remove(list.size() - 1);  
    }  
}

106 从中序与后序遍历序列构造二叉树、105 从前序与中序遍历序列构造二叉树

题目链接：(https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/)

不会，直接看解析

题目链接：(https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

更快的解法是把 inorder 放到 map 内，这样查找不用遍历。

public static TreeNode buildTree(int[] preorder, int[] inorder) {  
    if (preorder.length == 0) {  
        return null;  
    }  
    TreeNode root = new TreeNode(preorder[0]);  
    if (preorder.length == 1) {  
        return root;  
    }  
  
    int indexIn = -1;  
    for (int i = 0; i < inorder.length; i++) {  
        if (inorder[i] == preorder[0]) {  
            indexIn = i;  
            break;  
        }  
    }  
    // 左子树  
    int[] leftTreeInorder = Arrays.copyOfRange(inorder, 0, indexIn);  
    // 右子树  
    int[] rightTreeInorder = Arrays.copyOfRange(inorder, indexIn + 1, inorder.length);  
  
    root.left = buildTree(Arrays.copyOfRange(preorder, 1, leftTreeInorder.length + 1), leftTreeInorder);  
    root.right = buildTree(Arrays.copyOfRange(preorder, inorder.length - rightTreeInorder.length, inorder.length), rightTreeInorder);  
    return root;  
}

看解析

513 找树左下角的值

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0513.找树左下角的值.html)

那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

// 递归法
int value;  
int maxDeep = Integer.MIN_VALUE;  
public int findBottomLeftValueBFS(TreeNode root) {  
    value = root.val;  
    findLeftValue(root,0);  
    return value;  
}  
  
private void findLeftValue(TreeNode root, int deep) {  
    if (root == null) {  
        return;  
    }  
    if (root.left == null && root.right == null) {  
        if (deep > maxDeep) {  
            value = root.val;  
            maxDeep = deep;  
        }  
    }  
  
    if (root.left != null) {  
        findLeftValue(root.left, deep + 1);  
    }  
    if (root.right != null) {  
        findLeftValue(root.right, deep + 1);  
    }  
}

112 路径总和、113 路径总和 ii

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0112.路径总和.html)

绕晕了，如果把 targetSum -= root.val; 这句话写在函数最前面，就不用回溯。可以看三行简化的那个注释。我理解的是 Java 里 int 不能传递值，递归内层对 targetSum 的值进行改变，外层不会变化，所以就不用回溯了。

// 没搞懂怎么就不用回溯了，因为int不能传值吗？
/**  
 * 感觉之前做过求路径的题（递归+迭代）这题应该变换一下  
 * @param root 根节点  
 * @param targetSum 目标和  
 * @return 结果  
 */  
public static boolean hasPathSum(TreeNode root, int targetSum) {  
    if (root == null) {  
        return false;  
    }  
    targetSum -= root.val;  
    return hasPathSumBFS(root, targetSum);  
}  
  
private static boolean hasPathSumBFS(TreeNode root, int targetSum) {  
    if (root.left == null && root.right == null) {  
        // 求list中的总和  
        return targetSum == 0;  
    }  
  
    if (root.left != null) {  
        targetSum -= root.left.val;  
        if (hasPathSumBFS(root.left, targetSum)) {  
            return true;  
        }  
        // 这里的回溯就是把当前节点减掉（数值加上）。包括之前也是，但是之前是list不太好移除，所以选择移除最后一位
        targetSum += root.left.val;  
    }
    
	/*
	// 上面三行可以简化成  
	if (root.left != null) {  
	    // 这里targetSum的值是没有变化的。减完的值进入循环，就不用回溯了  
	    hasPathSumBFS(root.left, targetSum - root.left.val);  
	}
	*/
	
    if (root.right != null) {  
        targetSum -= root.right.val;  
        if (hasPathSumBFS(root.right, targetSum)) {  
            return true;  
        }  
        targetSum += root.right.val;  
    }  
  
    return false;  
}
/**  
 * 简化版本  
 */  
public static boolean hasPathSum(TreeNode root, int targetSum) {  
    if (root == null) {  
        return false;  
    }  
  
    if (root.left == null && root.right == null) {  
        return targetSum == 0;  
    }  
      
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);  
}

106 从中序与后序遍历序列构造二叉树、105 从前序与中序遍历序列构造二叉树

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html)

更快的解法是把 inorder 放到 map 内，这样查找不用遍历。

/**  
 * 1.后序最后一个节点为根节点  
 * 2.根据这个节点切割中序数组（节点前为左子树，节点后为右子树）  
 * 3.根据中序数组的切割切割后序数组  
 * 4.递归  
 * @param inorder 中序遍历结果  
 * @param postorder 后序遍历结果  
 * @return 树  
 */  
public static TreeNode buildTree(int[] inorder, int[] postorder) {  
    if (inorder.length != postorder.length) {  
        return null;  
    }  
  
    if (postorder.length == 0) {  
        return null;  
    }  
    TreeNode root = new TreeNode(postorder[postorder.length - 1]);  
    if (postorder.length == 1) {  
        return root;  
    }  
  
    int indexIn = -1;  
    for (int i = 0; i < inorder.length; i++) {  
        if (inorder[i] == postorder[postorder.length - 1]) {  
            indexIn = i;  
            break;  
        }  
    }  
    // 左子树  
    int[] leftTreeInorder = Arrays.copyOfRange(inorder, 0, indexIn);  
    // 右子树  
    int[] rightTreeInorder = Arrays.copyOfRange(inorder, indexIn + 1, inorder.length);  
  
    root.left = buildTree(leftTreeInorder, Arrays.copyOfRange(postorder, 0, leftTreeInorder.length));  
    root.right = buildTree(rightTreeInorder, Arrays.copyOfRange(postorder, leftTreeInorder.length, postorder.length - 1));  
    return root;  
}