二叉树——9.找树左下角的值

力扣题目链接

给定一个二叉树，在树的最后一行找到最左边的值。

示例：

输出：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作为node，1存在右子节点3，则当前队列为[3]，1存在左节点2，则当前队列为[3,2]。队列存在，弹出队列最左侧节点3作为node，3存在右子节点，则当前队列为[2,6]，3存在左子节点，则当前队列为[2,6,5]。队列存在，弹出最左侧节点2作为node，2只存在左子节点4，则当前队列为[6,5,4]。队列存在，弹出6作为node，6只存在右子节点7，则当前队列为[5,4,7]，一个个弹出，最后弹出7为最后的值。将该代码提交，结果也同样正确，所以在该题目中如果最下层只有一个节点，且该节点为右叶子，那这个右叶子算这棵树的左下角的值。