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

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

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

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

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

更多资料

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

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×