【Day 16】 找树左下角的值

题目描述

给定一个二叉树，在树的最后一行找到最左边的值。
 
示例 1:
 
输入:
 
    2
 
/ \
 1 3
 
输出:
1
示例 2:
 
输入:
 
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
 
输出:
7
​```
 
注意: 您可以假设树（即给定的根节点）不为 NULL。
 
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

https://github.com/leetcode-pp/91alg-1/issues/37#issuecomment-647883995

解法一

BFS

时间复杂度 O(n) n 指深度

空间复杂度 O(n +1) n 应该是最长的节点 +一个常量空间记录最左

通过 BFS 遍历所有节点，将每个 Level 的最左边节点更新给常量空间

var findBottomLeftValue = function (root) {
    let rust = root.val
    let curLevel = []
    if (root) curLevel.push(root)
    while (curLevel.length) {
        let nextLevel = []
        for (let i = 0; i < curLevel.length; i++) {
            let cur = curLevel[i]
            if (cur.left) nextLevel.push(cur.left)
            if (cur.right) nextLevel.push(cur.right)
        }
        if (nextLevel[0]) rust = nextLevel[0].val;
        curLevel = nextLevel
    }
    return rust
};

解法二

产品经理大法好

DFS

时间复杂度 O(n) n 指深度

空间复杂度 O(1) 2 个常数空间

var findBottomLeftValue = function (root) {
    let rust = root.val
    let maxDepth = 0
    let left = dfs(root.left, 0)
    let right = dfs(root.right, 0)
    function dfs(cur, depth) {
        if (!cur) return
        let curDepth = depth + 1
        if (curDepth > maxDepth) {
            maxDepth = curDepth
            rust = cur.val
        }
        dfs(cur.left, curDepth)
        dfs(cur.right, curDepth)
    }
    return rust
};

参考回答

BFS

其实问题本身就告诉你怎么做了

在树的最后一行找到最左边的值。

问题再分解一下

• 找到树的最后一行
• 找到那一行的第一个节点

不用层序遍历简直对不起这个问题，这里贴一下层序遍历的流程

令curLevel为第一层节点也就是root节点
定义nextLevel为下层节点
遍历node in curLevel,
  nextLevel.push(node.left)
  nextLevel.push(node.right)
令curLevel = nextLevel, 重复以上流程直到curLevel为空
var findBottomLeftValue = function (root) {
  let curLevel = [root];
  let res = root.val;
  while (curLevel.length) {
    let nextLevel = [];
    for (let i = 0; i < curLevel.length; i++) {
      curLevel[i].left && nextLevel.push(curLevel[i].left);
      curLevel[i].right && nextLevel.push(curLevel[i].right);
    }
    res = curLevel[0].val;
    curLevel = nextLevel;
  }
  return res;
};

DFS

树的最后一行找到最左边的值，转化一下就是找第一个出现的深度最大的节点，这里用先序遍历去做，其实中序遍历也可以，只需要保证左节点在右节点前被处理即可。
具体算法为，先序遍历 root，维护一个最大深度的变量，记录每个节点的深度，如果当前节点深度比最大深度要大，则更新最大深度和结果项

function findBottomLeftValue(root) {
  let maxDepth = 0;
  let res = root.val;
 
  dfs(root.left, 0);
  dfs(root.right, 0);
 
  return res;
 
  function dfs(cur, depth) {
    if (!cur) {
      return;
    }
    const curDepth = depth + 1;
    if (curDepth > maxDepth) {
      maxDepth = curDepth;
      res = cur.val;
    }
    dfs(cur.left, curDepth);
    dfs(cur.right, curDepth);
  }
}