当前位置：网站首页>LeetCode 每日一题——513. 找树左下角的值

LeetCode 每日一题——513. 找树左下角的值

2022-06-22 20:11:00 【SK_Jaco】

1.题目描述

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

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

示例 1:

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

示例 2:

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

2.解题思路与代码

2.1 解题思路

这道题要获取最左侧的节点值，其实就是在获取最后一层最左边第一个节点，因此考虑使用二叉树层序遍历解答。这里就需要使用到层序遍历的一个特点：放入队列的次数等于队列长度时，那么下一层已全部放入队列中。利用这一特性当放入次数等于队列长度时，此时从队列获取队头即是这一层的第一个节点，遍历完成之后便能得到最后一层第一个节点。这里使用数组来模拟一个队列。

2.2 代码

class Solution {
    
    public int findBottomLeftValue(TreeNode root) {
    
        int head = 0;
        int tail = 0;
        // 使用数组模拟队列
        TreeNode[] queue = new TreeNode[10000]; 
        queue[tail++] = root;
        int count = 1;
        TreeNode ans = null;
        while (tail - head > 0) {
    
            if (count == tail - head) {
    
                // 如果入队数等于队列中元素个数，则 ans 等于对头元素，并且计数清零
                ans = queue[head];
                count = 0;
            }
            // 弹出队头元素
            TreeNode poll = queue[head++];
            if (poll.left != null) {
    
                queue[tail++] = poll.left;
                count++;
            }
            if (poll.right != null) {
    
                queue[tail++] = poll.right;
                count++;
            }
        }
        return ans.val;
    }
}