【LeetCode】找树左下角的值 Java 题解

作者：Albert

2022 年 7 月 01 日
本文字数：1023 字
阅读完需：约 3 分钟

题目描述

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

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

示例 1:
输入: root = [2,1,3]输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]输出: 7
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/find-bottom-left-tree-value著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是二叉树处理题目，题目要求找出该二叉树的最底层最左边节点的值。
分析这个题目，我们需要找到二叉树的最底层，然后找到最左边。由于树的结构特殊，我们需要遍历整个二叉树，找到最底层的最左边节点。可以采用层序遍历的方式实现。专业的术语是 BFS，BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索，是图上最基础、最重要的搜索算法之一。
所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。实现代码如下，供参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int findBottomLeftValue(TreeNode root) {        int ans = 0;        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            int size = queue.size();            for (int i = 0; i < size; i++) {                TreeNode node = queue.poll();                if (i == 0) {                    ans = node.val;                }                if (node.left != null) {                    queue.offer(node.left);                }                if (node.right != null) {                    queue.offer(node.right);                }            }        }
        return ans;    }}