专业英文网站制作,阳城做网站,庆阳门户,物流网站怎么做推广513 找树左下角的值
给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1#xff1a; 示例 2#xff1a;
思路
层序遍历
直接层序遍历#xff0c;因为题目说了是最底层#xff0c;最左边的值请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1 示例 2
思路
层序遍历
直接层序遍历因为题目说了是最底层最左边的值所以就是层序遍历最后一层的第一个值。
class TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right# 法一 采用层序遍历
from collections import deque
class Solution(object):def findBottomLeftValue(self, root)::type root: TreeNode:rtype: intqueue deque([root])result []while queue:level_result []for _ in range(len(queue)):node queue.popleft()level_result.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(level_result)return result[-1][0] # 题目说了最底层层序遍历法很好理解
递归法
我们来分析一下题目在树的最后一行找到最左边的值。 首先要是最后一行然后是最左边的值。 如果使用递归法如何判断是最后一行呢其实就是深度最大的叶子节点一定是最后一行。 那么如何找最左边的呢可以使用前序遍历当然中序后序都可以因为本题没有 中间节点的处理逻辑只要左优先就行保证优先左边搜索相对右因为题目说是最左边的然后记录深度最大的叶子节点此时就是树的最后一行最左边的值。 递归三部曲
确定递归函数的参数和返回值
参数必须有要遍历的树的节点采用node一般化还有就是一个变量用来记录最长深度。 本题还需要类里的两个全局变量max_depth用来记录最大深度result记录最大深度最左节点的数值。采用slef初始化
# 1. 传入一个记录深度的变量 传入一个结点
def traversal(self, node, depth):# 2. 当结点是叶子结点的时候 就计算深度确定终止条件
当遇到叶子节点的时候就需要统计一下最大的深度了所以需要遇到叶子节点来更新最大深度。
# 中
if not node.left and not node.right:if depth self.max_depth:self.max_depth depthself.result node.val确定单层递归的逻辑
在找最大深度的时候递归的过程中依然要使用回溯代码如下
# 左
if node.left:depth 1self.traversal(node.left, depth)depth - 1 # 回溯# 右
if node.right:depth 1self.traversal(node.right, depth)depth - 1 # 回溯完整代码
# 法二 采用递归法 巧妙利用深度来判断是否是最后一行 前序遍历
class Solution(object):def findBottomLeftValue(self, root):self.max_depth float(-inf) # 记住写法self.result Noneself.traversal(root, 0) # 初始深度赋值为0return self.result# 因为需要遍历来判断深度 所以写一个新函数(也可以不用)# 1. 传入一个记录深度的变量 传入一个结点def traversal(self, node, depth):# 2. 当结点是叶子结点的时候 就计算深度# 中if not node.left and not node.right:if depth self.max_depth:self.max_depth depthself.result node.val# 左if node.left:depth 1self.traversal(node.left, depth)depth - 1 # 回溯# 右if node.right:depth 1self.traversal(node.right, depth)depth - 1 # 回溯参考 https://www.programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html