LeetCode算法解析：513. 找到树的左下角的值笔记

时间：11-16 名人轶事提交错误

图片.png

输出：

示例2:

输入：

图片.png

输出：

Note: 您可以假设树（即给定的根节点）不为NULL。

大意：

给定一个二叉树，找到树底行中最左边的节点值。

示例1：

进入：

图片.png

输出：

示例2：

进入：

图片.png

输出：

注意：您可以假设树（即给定根节点）非空。

思路：

这个问题其实可以分解为两个问题：

找到二叉树的底行；找到底行中最左边的节点值。需要说明的是，最左边的节点值不一定是左节点，也可以是最左边的右子节点值。

记得在传送门：LeetCode笔记：102.二叉树层序遍历中，我们要求逐层输出二叉树。然后通过同样的方法，我们使用BFS广度优先遍历的方法，利用队列保证底层的所有节点值都被找到，然后只需要使用一个标记来对位于的节点进行排序即可每次都是底层。记录左侧节点的值。这样，当确定是最后一层并且没有下一层时，我们记录的就是最低层最左边节点的值。

代码（Java）：

/**

* 二叉树节点的定义。

* 公共类树节点{

* int 值；

*左树节点；

*右树节点；

* TreeNode(int x) { val=x; }

* }

公共课解决方案{

公共int findBottomLeftValue(TreeNode root) {

Queuequeue=new LinkedList();

队列.offer(root);

int 结果=root.val;

布尔值有=false；

while (!queue.isEmpty()) {

int levelNum=队列.size();

for (int i=0; i levelNum; i++) {

if (queue.peek().left !=null) {

队列.offer(队列.peek().left);

如果（！有）{

结果=queue.peek().left.val;

有=真；

}

if (queue.peek().right !=null) {

队列.offer(队列.peek().right);

如果（！有）{

结果=queue.peek().right.val;

有=真；

}

队列.poll();

}

有=假；

}

返回结果；

}

他山之石：

我的方法其实比较慢。我们来看看下面的方法：

公共课解决方案{

公共int findBottomLeftValue(TreeNode root) {

返回findBottomLeftValue(root, 1, new int[]{0,0});

}

公共int findBottomLeftValue(TreeNode 根， int 深度， int[] res) {

if(res[1]方法的第一个好处就是代码确实比我的简单很多.他的做法其实和我第一个想法类似，用DFS向下递归查找，同时记录当前find 对于节点的深度，他使用了一个int数组res，数组的第一个元素记录了节点值，第二个元素记录了节点的深度，只有当进入更深的一层并且这一层还没有记录的时候。记录第一个找到的节点值，找到后，将深度标记为当前深度，那么后面找到的所有该深度的节点值将不再记录。除非找到更深的节点。这样继续下去，根据深度不断更新找到的节点值，最后找到最深层的最左边的节点值。