文章目录
- day18学习内容
- 一、找树左下角的值
- 1.1、思路
- 1.2、错误写法
- 1.2.1、为什么这么写是错的？
- 1.3、正确写法
- 二、路径总和
- 2.1、思路
- 2.2、正确写法1
- 2.2.1、这种写法回溯思想体现在哪里？
- 2.3、正确写法2
- 2.3.1、这种写法回溯思想体现在哪里？
- 2.4、求和解法，
- 三、中序后序构造二叉树
- 3.1 思路
- 3.2 代码
- 3.2.1、代码中切割中序数组跑哪里去了？
- 3.2.1、代码中切割后序数组跑哪里去了？
- 3.2.2、测试用例
- 总结
- 1.感想
- 2.思维导图
day18学习内容
day18主要内容
- 找树左下角的值
- 路径总和
- 中序后序构造二叉树
声明
本文思路和文字，引用自《代码随想录》
一、找树左下角的值
513.原题链接
1.1、思路
- 直接使用层序遍历，返回队列中第0个元素就是树的左下角
1.2、错误写法
class Solution {
public int findBottomLeftValue(TreeNode root) {
int result = 0;
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
if (root == null) {
return result;
}
deque.offer(root);
while (!deque.isEmpty()) {
for (int i = 0; i < deque.size(); i++) {
TreeNode node = deque.poll();
if (i == 0) {
result = node.val;
}
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return result;
}
}
1.2.1、为什么这么写是错的？
- 首先，层序遍历是每次循环只处理当前层的节点
- 然后，层序遍历，队列的大小是在动态变化的
- 使用的循环方式 for (int i = 0; i < deque.size(); i++) 实际上并不正确地处理每一层的节点，
- 因为在遍历过程中，队列的大小是动态变化的，这导致不能准确地一次处理完一层的所有节点。
- 正确的处理方式应该是在开始每一层的遍历之前，先记录下当前层的节点数量（也就是当前队列的大小），然后只处理这么多节点作为当前层的遍历，
- 因为在遍历当前层的同时，队列中会加入下一层的节点，
但这些下一层的节点应该在下一次循环中处理。
- 因为在遍历当前层的同时，队列中会加入下一层的节点，
1.3、正确写法
层序遍历
class Solution {
public int findBottomLeftValue(TreeNode root) {
int result = 0;
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
if (root == null) {
return result;
}
deque.offer(root);
while (!deque.isEmpty()) {
int size = deque.size(); // 当前层的节点数量
for (int i = 0; i < size; i++) {//只处理当前层的节点，非当前层不处理
TreeNode node = deque.poll();
// 更新结果值为当前层的第一个节点的值
if (i == 0) {
result = node.val;
}
// 将当前节点的左右子节点加入队列
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return result;
}
}
二、路径总和
112.原题链接
2.1、思路
- 本题体现了回溯的思想
2.2、正确写法1
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
targetSum -= root.val;
// 如果是叶子结点
if (root.left == null && root.right == null) {
return targetSum == 0;
}
// 左叶子节点
if (root.left != null) {
boolean left = hasPathSum(root.left, targetSum);
if (left) {
return true;
}
}
// 右叶子结点
if (root.right != null) {
boolean right = hasPathSum(root.right, targetSum);
if (right) {
return true;
}
}
return false;
}
}
2.2.1、这种写法回溯思想体现在哪里？
- 在这段代码中，回溯思想体现在递归探索每条从根节点到叶子节点的路径上，查找是否存在一条路径的节点值之和等于给定的targetSum。当探索一条路径（无论是向左还是向右子树深入）不满足条件时（即没有找到符合条件的路径），代码会自动“回溯”到上一个节点，然后尝试另一条路径。这里的“回溯”是隐式发生的，通过递归函数调用的返回来实现。
- 具体体现在以下几个方面：
- 递归减少targetSum：
- 每次递归调用都会将targetSum减去当前节点的值，这相当于“走过”了当前节点。如果到达叶子节点时，targetSum正好减为0，说明找到了一条满足条件的路径。
- 探索所有可能的路径：
- 如果当前节点不是叶子节点，代码会先尝试递归地探索左子树（if (root.left != null)），然后是右子树（if (root.right != null)）。这表示在每个非叶子节点，都会尝试所有可能的“前进”路径。
- 隐式回溯：
- 当递归调用探索左子树或右子树未找到满足条件的路径时（即这些调用返回false），程序会自动返回到当前节点，并尝试另一条可能的路径。
- 如果左子树未找到，就尝试右子树；如果左右子树都未找到，就返回到上层节点继续尝试。
- 这个过程是递归的自然特性，不需要显式的回溯操作（如撤销选择或更改状态），因为
每次递归调用都有自己的局部变量targetSum，这保证了返回上层递归时状态自然“回溯”。
- 终止条件：
- 如果达到一个叶子节点且targetSum减去该叶子节点的值后为0，则找到了一条符合条件的路径，返回true，并通过递归调用栈逐层向上返回，终止进一步的搜索。
- 递归减少targetSum：
2.3、正确写法2
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
// 如果当前节点为空，说明不存在路径，返回false
if (root == null) {
return false;
}
// 如果当前节点是叶子节点，并且其值等于剩余的目标值，则找到了一条路径，返回true
if (root.left == null && root.right == null && root.val == targetSum) {
return true;
}
// 否则，递归检查左右子树，更新目标值为目标值减去当前节点的值
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum - root.val);
}
}
2.3.1、这种写法回溯思想体现在哪里？
- 递归探索：通过递归地调用hasPathSum方法来探索从当前节点开始的所有可能路径。在每一层的递归中，程序尝试“前进”到左子树或右子树，同时更新剩余的目标值（即减去当前节点的值）。
- 路径的选择和撤销：在每次递归调用中，选择当前节点作为路径的一部分，并尝试继续向下探索（向左或向右）。如果从当前节点开始无论如何都不能达到目标和，递归调用会失败（返回false），然后自动“回撤”到上一节点，尝试另一种可能的路径。这个过程是通过递归调用栈的自然退回来实现的，而不需要显式地撤销选择。
- 逻辑上的回溯：当从一个节点向下探索未能找到满足条件的路径时（即左子树和右子树的递归调用都返回false），程序会自动返回到该节点的父节点，然后尝试另一条分支。这种从尝试失败的路径上“回到”之前的节点尝试其他路径的过程，是逻辑上的回溯，即尽管没有显式地修改任何状态或撤销选择，递归的返回过程实现了向上回溯
2.4、求和解法，
嗯这个是我自己一开始的思路，有点逆天吧
public class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
// 起始时，从根节点开始，路径和为0
return hasPathSum2(root, 0, targetSum);
}
private boolean hasPathSum2(TreeNode node, int currentSum, int targetSum) {
// 如果当前节点为空，返回false
if (node == null) {
return false;
}
// 将当前节点的值累加到当前的路径和上
currentSum += node.val;
// 检查当前节点是否是叶子节点并且当前路径和是否等于目标值
if (node.left == null && node.right == null) {
return currentSum == targetSum;
}
// 递归检查左右子节点，看是否存在符合条件的路径
return hasPathSumHelper(node.left, currentSum, targetSum)
|| hasPathSumHelper(node.right, currentSum, targetSum);
}
}
三、中序后序构造二叉树
106.原题链接
3.1 思路
- 第一步：空节点：如果数组大小为零的话，说明是空节点了。
- 第二步：后序数组最后一个元素作为节点元素。
- 第三步：寻找节点元素做切割点：找到后序数组最后一个元素在中序数组的位置，作为切割点
- 第四步：切割中序数组，切成中序左数组和中序右数组
- 第五步：切割后序数组，切成后序左数组和后序右数组
- 第六步：递归处理左区间和右区间
3.2 代码
class Solution {
// 用于存储中序遍历中元素的索引
Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
if (inBegin >= inEnd || postBegin >= postEnd) {
return null;
}
//获取根节点元素
int rootVal = postorder[postEnd - 1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = map.get(rootVal);
int leftNum = rootIndex - inBegin;
//这里省略了切割中序数组
root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + leftNum);
root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftNum, postEnd - 1);
return root;
}
}
3.2.1、代码中切割中序数组跑哪里去了？
切割中序数组：
中序数组被“切割”成左右子树的部分主要是在下面的代码中：
- 左子树的中序范围是从inBegin到rootIndex（不包括rootIndex）：
root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + leftNum);
这里的rootIndex是当前根节点在中序遍历数组中的索引。
左子树的中序范围是从当前范围的起始位置inBegin到根节点的位置rootIndex。
- 右子树的中序范围是从rootIndex + 1到inEnd：
root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftNum, postEnd - 1);
这里，从rootIndex + 1开始直到当前范围的结束位置inEnd，表示的是右子树在中序遍历数组中的部分。
3.2.1、代码中切割后序数组跑哪里去了？
切割后序数组：
后序数组的“切割”是为了分离出左右子树和根节点：
- 左子树的后序范围是从postBegin到postBegin + leftNum：
root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + leftNum);
这里，左子树的后序范围根据左子树的节点数leftNum确定，从postBegin开始，长度为leftNum。
- 树的后序范围是从postBegin + leftNum到postEnd - 1：
root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftNum, postEnd - 1);
这部分从左子树后序结束的下一个位置开始，到整个后序数组的最后一个元素之前（因为最后一个元素是当前根节点）。
通过这种方式，代码逻辑使用索引范围来模拟中序和后序数组的切割，为每次递归调用定位到当前子树对应的中序和后序遍历的部分，而无需实际创建子数组。
3.2.2、测试用例
public class Gouzao {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
static Map<Integer, Integer> map; // 方便根据数值查找位置
public static TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
System.out.println("初始化：中序遍历的值与索引映射已建立。map内容：" + map.toString());
System.out.println("开始构建二叉树...");
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
}
public static TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
if (inBegin >= inEnd || postBegin >= postEnd) {
System.out.println("递归结束条件达成，没有更多的元素可以用来构建二叉树节点。");
return null;
}
int rootVal = postorder[postEnd - 1]; // 后序遍历中最后一个元素是当前子树的根节点
TreeNode root = new TreeNode(rootVal);
int rootIndex = map.get(rootVal); // 在中序遍历中找到根节点的索引
System.out.printf("构建节点值为 %d 的根节点。在中序遍历中的索引为 %d。当前map内容：%s\n", rootVal, rootIndex, map.toString());
// 计算左子树中的元素数量
int leftNum = rootIndex - inBegin;
// 递归构建左子树
System.out.printf("递归构建值为 %d 的左子树，中序遍历范围：[%d, %d)，后序遍历范围：[%d, %d)，根节点在中序遍历中的索引：%d\n", rootVal, inBegin, rootIndex, postBegin, postBegin + leftNum, rootIndex);
root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + leftNum);
// 递归构建右子树
System.out.printf("递归构建值为 %d 的右子树，中序遍历范围：[%d, %d)，后序遍历范围：[%d, %d)，根节点在中序遍历中的索引：%d\n", rootVal, rootIndex + 1, inEnd, postBegin + leftNum, postEnd - 1, rootIndex);
root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftNum, postEnd - 1);
return root;
}
public static void main(String[] args) {
int[] inorder = new int[]{9,3,15,20,7};
int[] postorder = new int[]{9,15,7,20,3};
System.out.println(buildTree(inorder,postorder));
}
}
总结
1.感想
- 力扣的难度怪怪的，昨天的二叉树的所有路径是简单题，今天的第一题树的左下角的值却是中等题，无力吐槽了。
- 中序后序构造二叉树这题好难，不抄题解的话，我根本写不出来
2.思维导图
本文思路引用自代码随想录，感谢代码随想录作者。
