网站的营销方法,WordPress模板推荐国外,浙江大成建设集团网站,十大免费分销系统力扣题目链接
给定一个二叉树#xff0c;在树的最后一行找到最左边的值。
示例#xff1a; 输出#xff1a;7
题干很简单#xff0c;找到树的最后一行#xff0c;在该行找到最左边的值#xff0c;结合完整代码进行分析。
完整代码如下#xff1a;
class Solution:d…力扣题目链接
给定一个二叉树在树的最后一行找到最左边的值。
示例 输出7
题干很简单找到树的最后一行在该行找到最左边的值结合完整代码进行分析。
完整代码如下
class Solution:def findBottomLeftValue(self, root: TreeNode) - int:self.max_depth float(-inf)self.result Noneself.traversal(root, 0)return self.resultdef traversal(self, node, depth):if not node.left and not node.right:if depth self.max_depth:self.max_depth depthself.result node.valreturnif node.left:depth 1self.traversal(node.left, depth)depth - 1if node.right:depth 1self.traversal(node.right, depth)depth - 1
首先初始化max_depth用来记录当前访问到的最大深度。初始值设为负无穷大保证第一次遇到叶子节点时会更新深度。初始化一个属性result用来存储最底层最左边节点的值。调用辅助方法traversal开始递归遍历二叉树初始深度设为0。遍历完成后返回最底层最左边节点的值。
接着开始定义辅助函数traversal。 if not node.left and not node.right:if depth self.max_depth:self.max_depth depthself.result node.valreturn
检查当前节点是否是叶子节点即没有左子节点和右子节点。如果是叶子节点则进入下一层if如果当前节点的深度大于已记录的最大深度更新最大深度和结果值。更新max_depth为当前节点的深度更新result为当前节点的值。 if node.left:depth 1self.traversal(node.left, depth)depth - 1if node.right:depth 1self.traversal(node.right, depth)depth - 1
如果当前节点有左子节点递归遍历左子树。depth 1是一个计数操作将当前节点的深度增加1这表示我们正在进入二叉树的下一层。在递归调用之前增加深度是为了确保递归调用时能够正确地反映该节点在二叉树中的实际深度。
接着开始递归遍历左子树传入左子节点和更新后的深度一直递归调用直到到达叶子节点即没有子节点的节点为止。depth - 1是一个还原操作将深度恢复到递归调用之前的状态。这是为了确保在处理完左子树后能够正确地继续处理其他子树或返回到上一层节点。
右子树同理。
结合完整代码题目思路为一层一层向下探索直到找到叶子节点更新深度和结果。返回上一层进入另一子树继续递归只要发现深度更低的叶子结点就更新之前的深度和结果直到遍历完所有树。
但应该也有同学发现了在该代码中更新深度的条件只有是叶子节点且if depth self.max_depth那如果最下层只有一个节点且该节点为右叶子那这个右叶子算这棵树的左下角的值吗在该道题目中按上述代码进行提交结果是正确的所以在该题目中如果最下层只有一个节点且该节点为右叶子那这个右叶子算这棵树的左下角的值。
方法二队列迭代
from collections import dequeclass Solution:def findBottomLeftValue(self, root: TreeNode) - int:queue deque([root]) # 使用队列来进行广度优先搜索while queue:node queue.popleft() # 弹出当前层的节点# 这里重要的是先把右节点入队再把左节点入队if node.right:queue.append(node.right)if node.left:queue.append(node.left)# 最后弹出的 node 就是最后一层最左边的节点return node.val首先将根节点推入队列。只要队列中还有数就继续while循环把根节点从队列中弹出赋值给node如果当前node有右子树先将右子节点推入队列再将左子节点推入队列。先右后左这是为了保证每一层先将右侧的节点弹出。结合示例进行分析 1/ \2 3/ / \4 5 6\7初始队列为[1]队列存在数进入while循环弹出队列最左侧的数1作为node1存在右子节点3则当前队列为[3]1存在左节点2则当前队列为[3,2]。队列存在弹出队列最左侧节点3作为node3存在右子节点则当前队列为[2,6]3存在左子节点则当前队列为[2,6,5]。队列存在弹出最左侧节点2作为node2只存在左子节点4则当前队列为[6,5,4]。队列存在弹出6作为node6只存在右子节点7则当前队列为[5,4,7]一个个弹出最后弹出7为最后的值。将该代码提交结果也同样正确所以在该题目中如果最下层只有一个节点且该节点为右叶子那这个右叶子算这棵树的左下角的值。
