题目描述:给定一个二叉树,找出其最大深度。

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

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

# 解法 1: 递归

递归的写法非常直观。对于一棵二叉树来说,它的高度等于左右子树的高度最大值,加上 1。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
// 原文地址:https://xxoo521.com/2020-03-22-max-depth/
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
1
2
3
4
5
6
7
8
9
10

# 解法 2: 层序遍历

按照二叉树的“层”去遍历,最后返回层的数目。这题和《剑指 offer - 从上到下打印二叉树 III - JavaScript》思路完全一样。

细节请看代码注释,代码实现如下:

// ac地址:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
// 原文地址:https://xxoo521.com/2020-03-22-max-depth/
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (!root) return 0;
    let res = 0;
    const queue = [root];
    while (queue.length) {
        let levelNum = queue.length; // 当前层中二叉树的节点数量
        ++res;
        // 依次将下一层的二叉树节点放入队列
        while (levelNum--) {
            const node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

来自: 【LeetCode 104.二叉树的最大深度】双解法:递归+非递归 | 心谭博客
作者:心谭
Star仓库:github