【LeetCode 104.二叉树的最大深度】双解法：递归+非递归

心谭博客

发布于 2020-04-21 15:48:25

6370

发布于 2020-04-21 15:48:25

文章被收录于专栏：YuanXin

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

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

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

解法 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));
};

解法 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;
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-03-22，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树