LeetCode 513. Find Bottom Left T

@(LeetCode)

问题描述

给定一个二叉树，找出最后一层最左节点的值。

栗 1：

输入：

    2
   / \
  1   3

输出：
1

栗 2：

输入：

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出：
7

想看英文描述的戳这里。

注意：假定树的根节点不可能为空。

解题思路

这道题思路比较简单。

要想求出最后一层的最左节点值，只需按层从左往右遍历，并将最后一层节点保存下来，取第一个节点值即可。

js 代码如下：

var findBottomLeftValue = function (root) {
  if (root) {
    // 当前需要遍历节点
    let list = []
    list.push(root)

    while (list.length > 0) {
      // 存储下一层数据
      let tmp = []
    
      // 逐个遍历，取下一层节点
      let i = 0
      while (i < list.length) {
        const node = list[i]

        // 压入左子树
        if (node.left) {
          tmp.push(node.left)
        }

        // 压入右子树
        if (node.right) {
          tmp.push(node.right)
        }

        i += 1
      }

      // 把下一层数据赋值给 list
      if (tmp.length > 0) {
        list = tmp
      } else {
        break
      }
    }

    // 取最后一层的第一个数据
    if (list.length > 0) {
      const node = list[0]
      return node.val
    }
  }

  return null
};

其实还有另外一种方法，也是层遍历，只不过是从右往左。记录最后取出的节点值，即为最后一层的最左节点。

js 代码如下：

var findBottomLeftValue = function (root) {
  if (root) {
    let list = []
    list.push(root)

    // 记录取出的节点
    let node

    while (list.length > 0) {

      // 取第一个元素
      node = list.shift()

      // 压入右子树
      if (node.right) {
        list.push(node.right)
      }

      // 压入左子树
      if (node.left) {
        list.push(node.left)
      }
    }

    return node.val
  }

  return null
};