Skip to content

Latest commit

 

History

History
319 lines (245 loc) · 7.47 KB

16.find-bottom-left-tree-value.md

File metadata and controls

319 lines (245 loc) · 7.47 KB

513.找树左下角的值

https://leetcode-cn.com/problems/find-bottom-left-tree-value/

题目描述

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

示例 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：BFS

思路

按照题目意思来做，找到最后一层，返回最左边的节点。

所以只要，对二叉树进行层次遍历，遍历到最后一层的时候，返回第一个节点就行了。

bfs

伪代码

层次遍历模板 1：

新建 curLevel 数组保存当前层的节点；
新建 nextLevel 数组保存下一层要遍历的节点；

将 root 加入到 curLevel 中，开始遍历；

重复以下操作：
    遍历 curLevel 中的节点：
        如果该节点存在左子节点，把左子节点加入到 nextLevel 中；
        如果该节点存在右子节点，把右子节点加入到 nextLevel 中；

    判断 nextLevel 中是否有节点：
        如果没有，说明已经遍历到树的最深层次，此时 curLevel 中放的是最深层的所有叶子节点，返回第一个即可；

    让 nextLevel 作为下一个循环中要遍历的对象，即 curLevel = nextLevel；
    将 nextLevel 清空；

层次遍历模板 2：

const queue = [root];

while (queue.length) {
    // 先记录这一层的节点数
    let len = queue.length;

    while (len--) {
        const node = queue.shift();
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
}

代码

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let curLevel = [root],
        nextLevel = [];

    while (true) {
        for (let node of curLevel) {
            node.left && nextLevel.push(node.left);
            node.right && nextLevel.push(node.right);
        }

        if (!nextLevel.length) return curLevel[0].val;

        curLevel = nextLevel;
        nextLevel = [];
    }
};

Python Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        curLevel, nextLevel = [root], []
        while True:
            for node in curLevel:
                if node.left: nextLevel.append(node.left)
                if node.right: nextLevel.append(node.right)
            if not nextLevel: return curLevel[0].val
            curLevel, nextLevel = nextLevel, []

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    if (!root) return 0;

    const queue = [root];
    let bottomLeft = null;
    while (queue.length) {
        let len = queue.length;

        // 每遍历一层就更新一次最左节点
        // 最后一层更新就是最后一层的的最左节点
        bottomLeft = queue[0];

        while (len--) {
            const node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return bottomLeft.val;
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 N 为节点数。
  • 空间复杂度: O ( q ) ，q 为队列长度。最坏情况是满二叉树，此时 q 为 2 / N ，即为 O ( N ) ，N 为二叉树节点数。

方法 2：DFS

思路

想一下递归的路线，如果我们先递归遍历左子树再遍历右子树，那么每遍历到新一层的时候，都是先访问最左边的节点。

  • 所以我们只需要在遍历到新一层的时候，记录第一个节点。
  • 用 depth 来记录当前层次，用 maxDepth 来记录已经遍历过的最深层次，当 depth > maxDepth 的时候，说明遍历到了新层次：
    • 记录第一个节点的值
    • 更新 maxDepth

伪代码

创建 ans 来记录遍历中遇到的最左边的子节点
创建 maxDepth 来记录已经遍历到的最深层次

定义一个 dfs 函数来遍历二叉树，函数接收 (node, depth) 两个参数，node 是当前遍历到的节点，depth 是当前遍历深度：
    如果 node 为 null，终止遍历

    // 因为我们是先遍历左子节点，再遍历右子节点
    // 所以第一次 depth > maxDepth 的时候，遍历到的就是 depth 这一层最左边的子节点
    // 接着我们更新 maxDepth，之后遍历同一 depth 的节点时，ans 都不会更新了
    如果当前层级 depth > maxDepth：
        更新 ans 为 node.val
        更新 maxDepth 为 depth

    // 分别递归遍历左右子树
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)

调用 dfs 函数，传入 (root, 0)
返回 ans

复杂度分析

  • 时间复杂度：$O(N)$，其中 N 为节点数。
  • 空间复杂度：$O(h)$，其中 h 为树的深度，最坏的情况 h 等于 N ，其中 N 为节点数，此时树退化到链表。

代码

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let maxDepth = 0;
    let ans = 0;
    helper(root, 1);
    return ans;

    // ******************************

    function helper(root, depth) {
        if (!root) return 0;

        if (depth > maxDepth) {
            maxDepth = depth;
            ans = root.val;
        }

        helper(root.left, depth + 1);
        helper(root.right, depth + 1);
    }
};

Python Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    _ans = 0
    _maxDepth = 0

    def helper(self, root, depth):
        if root is None: return 0

        if depth > self._maxDepth:
            self._maxDepth = depth
            self._ans = root.val

        self.helper(root.left, depth + 1)
        self.helper(root.right, depth + 1)

    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root, 1)
        return self._ans