【刷题日记】513. 找树左下角的值

本次刷题日记的第 74 篇，力扣题为：513. 找树左下角的值，中等

一、题目描述：

查找树的左下角的节点，看看我们可以如何去查找呢，如何找更好更高效

二、这道题考察了什么思想？你的思路是什么？

查找树的左下角的节点，提炼一下重点信息：

• 题目中会给出一棵树，展示显示是用数组来表示的，二叉树的节点元素是整型的数字
• 给出的这一棵树，至少会有 1 个节点，也就是说，不会给我们一颗空树，至少都是有根的
• 要求我们找到这棵树的最底层最左边的节点元素

分析

我们通过已知消息和目标，我们自然而然油然而生出第一感觉是必然要遍历二叉树，那么我们先来看看遍历二叉树都有哪些方式

咱们可以按照树深度这个维度来遍历，那么我们可以使用深度优先算法

如果我们关注的是层序比那里的话，那么我们可以使用广度优先算法

深度优先算法

其实看到题第一反应，我想到的是广度优先算法，毕竟有点条件反射了，看到题目中需要我们找的是二叉树的最后一层的元素

回过头来看，优先算法的话，我们可以如何来处理呢？

如上图所示，我们其实就可以找到深度最深的一层，并且找到的是最左边的节点，那么如何找到最左边的节点呢？

这就有赖于我们在使用深度优先算法的时候注意细节了，我们可以先遍历节点的左子树，再遍历节点的右子树，遍历的时候，我们会记录当前的树高度，当遍历到下一层的时候，树高度就 +1， 那么先遍历左子树的原因是

如果是达到一个新的深度，那么一定是左子树先达到这个高度，那么咱们记录下来的必然是最左边的节点，当然如果最深的一层不是左子树，而是右子树，也不妨碍我们的逻辑

对于深度优先算法的话，感兴趣的兄弟可以实现一波

广度优先算法

那么广度优先算法的话，如何实现呢？

其实能够使用深度优先算法的地方必然是可以使用广度优先算法的，就看你喜欢使用哪一种思想了

对于广度优先算法，其实我们可以理解为就是层序遍历，一层一层给去遍历二叉树的每一层节点，一般咱们的实现方式是使用队列的方式，队列都是先进先出的 FIFO

那么对于这么一棵树，咱们层序遍历的话，其实可以从树的右子树开始遍历，再遍历左子树，那么，咱们再队列出队的最后一个元素的时候，就是咱们要找的最深一层的最左边的一个元素的

有没有感觉，对于这个题来说，广度优先算法，更加容易和适合

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

实现编码的时候注意咱们广度优先遍历二叉树的时候是从右边往左边遍历，最后取队列中的最后一个元素即可

编码如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    que := []*TreeNode{ root }
    var node  *TreeNode
    for len(que) > 0 {
        node = que[0]
        // 出队
        que = que[1:]
        if node.Right != nil {
            que = append(que, node.Right)
        }
        if node.Left != nil{
            que = append(que, node.Left)
        }
    }
    return node.Val
}   

四、总结：

咱们这种广度优先的实现方式，一层一层的去遍历这一棵树，时间复杂度很很明显，咱们是遍历了所有节点的，时间复杂度是 O(n)

这里的空间复杂度也是 O(n) ，因为咱们开辟的 que 队列占空了 O(n) 级别的空间消耗

原题地址：513. 找树左下角的值

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~