Medium

题目描述

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

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

示例 1:

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

示例 2:

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

提示:

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

解题思路

解题思路

这道题要求找到二叉树最底层最左边的节点值。我们可以采用以下两种方法：

方法一：层序遍历（推荐） 使用 BFS 层序遍历，从左到右遍历每一层。由于我们从左到右遍历，每一层的第一个节点就是该层最左边的节点。当遍历完成时，最后记录的"每层第一个节点"就是最底层最左边的节点。

具体步骤：

  1. 使用队列进行层序遍历
  2. 对于每一层，记录该层的第一个节点值
  3. 遍历完成后，最后记录的值即为答案

方法二：深度优先搜索 使用 DFS 遍历，记录每个节点的深度。优先遍历左子树，这样对于每个深度，第一次访问到的节点就是该层最左边的节点。维护一个最大深度变量，当发现更深的层时，更新答案。

两种方法时间复杂度相同，但层序遍历的思路更直观，代码也更简洁。

代码实现

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int leftmost = root->val;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                if (i == 0) {
                    leftmost = node->val;
                }
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return leftmost;
    }
};

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        from collections import deque
        
        queue = deque([root])
        leftmost = root.val
        
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                
                if i == 0:
                    leftmost = node.val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return leftmost

public class Solution {
    public int FindBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int leftmost = root.val;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                
                if (i == 0) {
                    leftmost = node.val;
                }
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
        }
        
        return leftmost;
    }
}

var findBottomLeftValue = function(root) {
    const queue = [root];
    let leftmost = root.val;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (i === 0) {
                leftmost = node.val;
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return leftmost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树中的每个节点一次，其中 n 是节点数量
空间复杂度O(w)w 是树的最大宽度，在最坏情况下（完全二叉树）为 O(n/2) = O(n)