0513. 找树左下角的值【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

给定一个二叉树的 根节点 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

2. 🎯 s.1 - BFS

c

int findBottomLeftValue(struct TreeNode* root) {
    struct TreeNode* queue[10000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int res = root->val;
    while (front < rear) {
        int size = rear - front;
        res = queue[front]->val;
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = queue[front++];
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
    }
    return res;
}

js

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
  let res = root.val
  const queue = [root]
  while (queue.length) {
    const size = queue.length
    res = queue[0].val
    for (let i = 0; i < size; i++) {
      const node = queue.shift()
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }
  return res
}

py

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

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 层序遍历，每层记录第一个节点的值
• 遍历结束后即为最底层最左边的值