跳到主要内容

LCR 045.找树左下角的值

· 阅读需 2 分钟

1、题干​

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

 

提示:

  • 二叉树的节点个数的范围是 [1,104]
  • -231 <= Node.val <= 231 - 1 

 

注意：本题与主站 513 题相同： https://leetcode-cn.com/problems/find-bottom-left-tree-value/

执行结果​

2.png

解题思路​

总体思路：使用DFS递归遍历树的所有节点，当第一次遍历到层级大于所有已遍历节点的节点时，该节点就是当前层级的最左子节点；随着遍历层级递增，最终能找到最底层的最左子节点。

  • 使用DFS递归遍历树的所有节点
  • 记录当前节点的层级level与已遍历节点的最大层级maxLevel
  • 每当level超过maxLevel时，将当前节点赋值给res，另外更新maxLevel
  • 遍历完成后，res就是要找的节点，返回该节点的值即可

代码​

var findBottomLeftValue = function (root) {
    let res, maxLevel = 0;
    function dfs(node, level) {
        if (!node) return;
        if (level > maxLevel) res = node, maxLevel = level;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 1);
    return res && res.val;
};