【Day 13 】2021-05-22 - 104. 二叉树的最大深度

题目描述

入选理由

1. 这是一个难度为 easy 的题目，适合作为第一题。
2. 此题适合练习递归。
3. 这是一个非常常见的考点，只不过有的时候是作为题目的一部分出现，而不是单独考察而已。

题目描述

定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(1)

前序遍历

var maxDepth = function (root, max = 0) {
    if (!root) return max
    return Math.max(maxDepth(root.left, max + 1),
        maxDepth(root.right, max + 1))
};

解法二

时空复杂度

时间复杂度：O(n) 每个节点进出一次

空间复杂度: O(n) 一层最大值

层序遍历

var maxDepth = function (root) {
    if (!root) return 0
    let queen = [root]
    let result = 0
 
    while (queen.length) {
        const length = queen.length
        console.log(length)
        result += 1
        for (let i = 0; i < length; i++) {
            const curr = queen.shift()
            if (curr.left) queen.push(curr.left)
            if (curr.right) queen.push(curr.right)
        }
    }
    return result
};

参考回答

• 官方题解
• 精选题解
• 精选题解