1. 题目描述

给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:

  1. 输入:
  2.     2
  3.    / \
  4.   1   3
  5. 输出:1

示例 2:

  1. 输入:
  2.         1
  3.        / \
  4.       2   3
  5.      /   / \
  6.     4   5   6
  7.        /
  8.       7
  9. 输出:7

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

2. 解题思路

这里可以对二叉树进行层序遍历，而层序遍历就是基于广度优先遍历的。

在遍历的过程中，我们初始化一个队列来保存当前层的节点，这个过程中，需要先将根节点的右子节点加入到队列中，再将其左子节点加入到队列中。

这个过程中，将对列元素出队，并加入到res数组中，这样数组的最后一个值就是二叉树左下角的值。

复杂度分析：

  • 时间复杂度：O(n)，其中n是二叉树的节点数，我们需要遍历整棵树；

  • 空间复杂度：O(n)，其中n是二叉树的高度，我们需要初始化一个数组来保存二叉树的所有节点；**

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val, left, right) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.left = (left===undefined ? null : left)
    6. *     this.right = (right===undefined ? null : right)
    7. * }
    8. */
    9. /**
    10. * @param {TreeNode} root
    11. * @return {number}
    12. */
    13. var findBottomLeftValue = function(root) {
    14.   const queue = [root]
    15.   let res = []
    17.   while(queue.length){
    18.       const node = queue.shift()
    19.       res.push(node.val)
    20.       node.right && queue.push(node.right)
    21.       node.left && queue.push(node.left)
    22.   }
    23.   return res[res.length - 1]
    24. };

    4. 提交结果

    image.png
    **