代码随想录训练营 Day16打卡 二叉树 part04 513. 找树左下角的值 112. 路径总和 106. 从中序与后序遍历序列构造二叉树

代码随想录训练营 Day16打卡 二叉树 part04

一、 力扣513. 找树左下角的值

给定一个二叉树，判断它是否是 平衡二叉树
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 ：
输入: root = [2,1,3]
输出: 1

思路分析

1. 确定递归函数的参数和返回值：

   参数：需要一个当前节点 root 和一个整数 depth 表示当前节点所在的深度。
   返回值：不需要返回值，因为我们只需要更新全局变量即可。

2. 确定终止条件：

   当节点为空时，递归结束。
   当遇到叶子节点时，需要更新最大深度和对应的节点值。

3. 确定单层递归的逻辑：

   更新最大深度和对应的节点值。
   递归遍历左右子树，并增加深度。

版本一 递归法 + 回溯

实现思路：使用递归+回溯方法遍历整棵树，通过比较深度找出最底层的最左边节点的值。递归中包括深度的增减来确保正确计算每个节点的深度。

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:self.max_depth = float('-inf')  # 初始化最大深度为负无穷大self.result = None  # 存放结果self.traversal(root, 0)  # 从根节点开始遍历return self.result  # 返回最底层最左边的节点值def traversal(self, node, depth):if not node.left and not node.right:# 如果是叶子节点if depth > self.max_depth:# 如果当前深度大于已记录的最大深度self.max_depth = depth  # 更新最大深度self.result = node.val  # 更新结果为当前叶子节点的值returnif node.left:depth += 1  # 增加深度self.traversal(node.left, depth)  # 遍历左子树depth -= 1  # 回溯，恢复深度if node.right:depth += 1  # 增加深度self.traversal(node.right, depth)  # 遍历右子树depth -= 1  # 回溯，恢复深度

版本二 递归法+精简

实现思路：类似版本一，但是简化了代码，去除了不必要的深度回溯操作。直接在递归调用时增加深度，更为简洁。

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:self.max_depth = float('-inf')  # 初始化最大深度为负无穷大self.result = None  # 存放结果self.traversal(root, 0)  # 从根节点开始遍历return self.result  # 返回最底层最左边的节点值def traversal(self, node, depth):if not node.left and not node.right:# 如果是叶子节点if depth > self.max_depth:# 如果当前深度大于已记录的最大深度self.max_depth = depth  # 更新最大深度self.result = node.val  # 更新结果为当前叶子节点的值returnif node.left:self.traversal(node.left, depth+1)  # 递归遍历左子树，直接增加深度if node.right:self.traversal(node.right, depth+1)  # 递归遍历右子树，直接增加深度

版本三 迭代法

实现思路：使用迭代的方式进行层序遍历（广度优先搜索），利用队列存储每一层的节点。记录每层的第一个节点的值，队列完成遍历后，最后记录的值即为最底层最左边的节点值。

from collections import deque
class Solution:def findBottomLeftValue(self, root):if root is None:return 0  # 如果根节点为空，则返回0queue = deque()  # 使用队列进行广度优先搜索queue.append(root)  # 加入根节点result = 0  # 初始化结果while queue:size = len(queue)  # 当前层的节点数for i in range(size):node = queue.popleft()  # 取出队列前端节点if i == 0:result = node.val  # 记录每层的第一个节点值if node.left:queue.append(node.left)  # 左子节点入队if node.right:queue.append(node.right)  # 右子节点入队return result  # 循环结束时，result即为最底层最左边的节点值

力扣题目链接
题目文章讲解
题目视频讲解

二、 力扣112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 ：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。

版本一 递归法

实现思路：这个版本通过递归遍历树的所有路径，并使用回溯来恢复计数状态。对于每个节点，若其为叶子节点且当前计数为0，则找到了有效路径。

class Solution:def traversal(self, cur: TreeNode, count: int) -> bool:if not cur.left and not cur.right and count == 0:  # 如果当前节点是叶子节点且计数为0return True  # 找到符合条件的路径if not cur.left and not cur.right:  # 如果是叶子节点但计数不为0return False  # 当前路径不符合条件if cur.left:  # 如果存在左子节点count -= cur.left.val  # 减去左子节点的值if self.traversal(cur.left, count):  # 递归检查左子树return True  # 如果找到符合条件的路径，返回Truecount += cur.left.val  # 回溯，恢复原来的计数值if cur.right:  # 如果存在右子节点count -= cur.right.val  # 减去右子节点的值if self.traversal(cur.right, count):  # 递归检查右子树return True  # 如果找到符合条件的路径，返回Truecount += cur.right.val  # 回溯，恢复原来的计数值return False  # 如果左右子树都没有找到符合条件的路径，返回Falsedef hasPathSum(self, root: TreeNode, sum: int) -> bool:if root is None:return False  # 如果根节点为空，直接返回Falsereturn self.traversal(root, sum - root.val)  # 从根节点开始遍历，初始化计数为sum减去根节点的值

版本二 递归 + 精简

实现思路：这个版本简化了递归函数，去除了显式的回溯操作，直接在递归调用中更新sum。检查每个叶子节点时，如果剩余的sum等于节点的值，说明找到了一条有效路径。

class Solution:def hasPathSum(self, root: TreeNode, sum: int) -> bool:if not root:return False  # 如果节点为空，返回Falseif not root.left and not root.right and sum == root.val:return True  # 如果是叶子节点且剩余的sum等于节点值，返回True# 递归检查左右子树，更新sum为sum减去当前节点的值return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

版本三 迭代法

实现思路：使用栈来迭代地遍历树，检查每个叶子节点的路径和是否等于sum。这种方法不需要递归调用，使用显示的栈来保存每个节点的状态。

class Solution:def hasPathSum(self, root: TreeNode, sum: int) -> bool:if not root:return False  # 如果根节点为空，返回Falsest = [(root, root.val)]  # 使用栈，初始化包含根节点和其值while st:node, path_sum = st.pop()  # 弹出一个元素# 检查是否为叶子节点且路径和等于sumif not node.left and not node.right and path_sum == sum:return True  # 如果符合条件，返回True# 将子节点压栈，并更新路径和if node.right:st.append((node.right, path_sum + node.right.val))if node.left:st.append((node.left, path_sum + node.left.val))return False  # 如果栈为空也没有找到有效路径，返回False

力扣题目链接
题目文章讲解
题目视频讲解

三、 力扣106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 ：

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
流程如图：

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

• 第一步：如果数组大小为零的话，说明是空节点了。
• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
• 第五步：切割后序数组，切成后序左数组和后序右数组
• 第六步：递归处理左区间和右区间

代码实现

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:# 特殊情况处理: 如果前序遍历结果为空，则二叉树也必然为空if not preorder:return None# 前序遍历的第一个元素为当前的根节点root_val = preorder[0]root = TreeNode(root_val)  # 创建根节点# 在中序遍历中找到根节点的位置，这个位置将数组分为左右两部分separator_idx = inorder.index(root_val)# 根据中序遍历中根节点的位置，切割中序数组，得到左子树和右子树的中序遍历结果inorder_left = inorder[:separator_idx]inorder_right = inorder[separator_idx + 1:]# 根据中序遍历中左子树的节点数量，切割前序数组，得到左子树和右子树的前序遍历结果# 前序遍历的左子树的长度与中序遍历的左子树长度相同preorder_left = preorder[1:1 + len(inorder_left)]preorder_right = preorder[1 + len(inorder_left):]# 递归构建左子树和右子树root.left = self.buildTree(preorder_left, inorder_left)root.right = self.buildTree(preorder_right, inorder_right)# 返回构建好的树的根节点return root

力扣题目链接
题目文章讲解
题目视频讲解