0513. 找树左下角的值 #
- 标签:树、深度优先搜索、广度优先搜索、二叉树
- 难度:中等
题目大意 #
描述:给定一个二叉树的根节点 root
。
要求:找出该二叉树 「最底层」的「最左边」节点的值。
说明:
- 假设二叉树中至少有一个节点。
- 二叉树的节点个数的范围是 $[1,10^4]$。
- $-2^{31} \le Node.val \le 2^{31} - 1$。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:层序遍历 #
这个问题可以拆分为两个问题:
- 如何找到「最底层」。
- 在「最底层」如何找到最左边的节点。
第一个问题,我们可以通过层序遍历直接确定最底层节点。而第二个问题可以通过改变层序遍历的左右节点访问顺序从而找到「最底层」的「最左边节点」。具体方法如下:
- 对二叉树进行层序遍历。每层元素先访问右节点,再访问左节点。
- 当遍历到最后一个元素时,此时最后一个元素就是「最底层」的「最左边」节点,即左下角的节点,将该节点的值返回即可。
思路 1:层序遍历代码 #
|
|