怎么做跳转不影响原网站排名,厦门建设与管理局官网,wordpress什么主题好用,哪个浏览器可以进wordpress给定一个二叉树#xff0c;在树的最后一行找到最左边的值。
示例 1: 示例 2: 思路#xff1a;
深度最大的叶子结点一定是最后一行。
优先左边搜索#xff0c;记录深度最大的叶子节点#xff0c;此时就是树的最后一行最左边的值 代码#xff1a;
class Solution:def fi…给定一个二叉树在树的最后一行找到最左边的值。
示例 1: 示例 2: 思路
深度最大的叶子结点一定是最后一行。
优先左边搜索记录深度最大的叶子节点此时就是树的最后一行最左边的值 代码
class Solution:def findBottomLeftValue(self, root: TreeNode) - int:# 初始化最大深度为负无穷表示尚未找到任何节点self.max_depth float(-inf)# 初始化结果为Noneself.result None# 调用遍历函数从根节点开始初始深度为0self.traversal(root, 0)# 返回最终结果即最底层最左边的节点值return self.resultdef traversal(self, node, depth):# 如果节点为空直接返回if not node:return# 如果当前节点是叶子节点没有左子节点和右子节点if not node.left and not node.right:# 如果当前深度大于最大深度更新最大深度和结果if depth self.max_depth:self.max_depth depthself.result node.valreturn# 先遍历左子树并将深度加1if node.left:self.traversal(node.left, depth 1)# 再遍历右子树并将深度加1if node.right:self.traversal(node.right, depth 1)以下为详细逐步讲解
1. 类和方法定义
class Solution:def findBottomLeftValue(self, root: TreeNode) - int:定义一个名为 Solution 的类其中包含一个方法 findBottomLeftValue。该方法接受一个二叉树的根节点 root 作为参数并返回树中最底层最左边的节点的值。
2. 初始化变量 self.max_depth float(-inf)self.result None初始化 max_depth 为负无穷大以便后续比较时任何节点的深度都会大于这个初始值。result 初始化为 None用于存储最底层最左边节点的值。
3. 调用遍历函数 self.traversal(root, 0)return self.result调用 traversal 方法从根节点开始遍历初始深度为0。遍历完成后返回 result。
4. 定义遍历函数 def traversal(self, node, depth):定义一个辅助函数 traversal用于递归遍历二叉树。该函数接受一个节点 node 和当前深度 depth 作为参数。
5. 节点为空的情况 if not node:return如果当前节点为空直接返回。
6. 叶子节点处理 if not node.left and not node.right:if depth self.max_depth:self.max_depth depthself.result node.valreturn如果当前节点是叶子节点即没有左子节点和右子节点检查当前深度是否大于最大深度。如果是更新 max_depth 和 result。然后返回因为叶子节点没有子节点遍历到此结束。
7. 遍历左子树 if node.left:self.traversal(node.left, depth 1)如果存在左子节点递归遍历左子树并将深度加1
8. 遍历右子树 if node.right:self.traversal(node.right, depth 1)如果存在右子节点递归遍历右子树并将深度加1 这段代码通过深度优先搜索DFS的方法遍历二叉树并在遍历过程中记录最底层最左边节点的值。
