513. 找树左下角的值

题目

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

• 二叉树的节点个数的范围是 [1,10^4]
• -2^31 <= Node.val <= 2^31 - 1

解答

思路

使用层序遍历到最后一层，返回第一个数。

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        cur = [root]

        while cur:
            nxt = []
            
            for node in cur:
                if node.left:
                    nxt.append(node.left)
                
                if node.right:
                    nxt.append(node.right)
            
            if not nxt:
                break

            cur = nxt

        return cur[0].val

思路：从右往左层序遍历

从右往左遍历：先入队右儿子，再入队左儿子。最后一个出队的就是所求的数。

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])

        while q:
            node = q.popleft()

            if node.right:
                q.append(node.right)

            if node.left:
                q.append(node.left)
        
        return node.val

Python 中：

• 模块（module），类（class）以及函数（def、lambda）才会引入新的作用域
• 其它的代码块（如 if、try、for 等）是不会引入新的作用域

思路：深度优先搜索

• height 记录节点高度
• cur_height 记录当前高度（每次到达新高度就更新它和 cur_val 即可）
• cur_val 记录当前高度下最左的节点

代码

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        cur_val = cur_height = 0

        def dfs(node: Optional[TreeNode], height: int) -> None:
            if node is None:
                return
            
            height += 1

            dfs(node.left, height)
            dfs(node.right, height)

            nonlocal cur_val, cur_height

            if height > cur_height:
                cur_height = height
                cur_val = node.val
            
        dfs(root, 0)

        return cur_val