📃 题目描述

题目链接：

• 剑指 Offer II 045. 二叉树最底层最左边的值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 513. 找树左下角的值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

示例 1:

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

示例 2:

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

🔔 解题思路

注意，这里是最底层最左边的节点，没有特别说明一定得是左孩子，所以这题就变得很简单了，直接层序遍历，最后一层的第一个节点就是题目要的结果

那么，如何找到最后一层的第一个节点呢？

我们使用一个变量记录 res 每层的第一个节点即可，每遍历一层，这个变量就会被重新赋值一次。这样，整颗树遍历结束后，这个变量 res 就指向最后一层的第一个节点

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);

        // 记录每层的第一个节点
        int res = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                TreeNode cur = queue.poll();
                if (i == 0) {
                    res = cur.val;
                }

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)