【基础篇 - Day 13】 2023-02-25 - 104. 二叉树的最大深度 （03. 树 ）

[threedayAAAAA]

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

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

[threedayAAAAA]

思路一

思路

层序遍历

代码

function maxDepth(root: TreeNode | null): number {
    let result = 0
    if(!root){
        return result
    }
    let floor = [root]
    while(floor.length){
        let newFloor = []
        floor.forEach(item => {
            if(item.left) newFloor.push(item.left)
            if(item.right) newFloor.push(item.right)
        })
        floor = newFloor
        result++
    }
    return result
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度: O(Max(Len(floor)))

思路二

思路

深序遍历

代码

function maxDepth(root: TreeNode | null, dep = 0): number {
    if(!root){
        return dep
    }
    return Math.max(maxDepth(root.left, dep + 1), maxDepth(root.right, dep + 1))
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度： O(N) 二叉树的最大深度

[yunliuyan]

思路

• DFS算法
• 递归左右树节点，每次递归返回值加1，对比左右节点大小

代码

function maxDepth(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);

    return Math.max(left, right) + 1;
};

复杂度分析

时间复杂度: O(n) 空间复杂度: O(n)

[MiumMi]

思路

层序遍历，记录有多少层，然后返回即可

代码

function maxDepth(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    let queue = [root];
    let index = 0;
    while(queue.length) {
        const currentLevel = queue;
        queue = [];
        for (let i = 0; i < currentLevel.length; i++) {
            const tempVal = currentLevel[i];
            if (tempVal.left) {
                queue.push(tempVal.left);
            }
            if (tempVal.right) {
                queue.push(tempVal.right);
            }
        }
        index++;
    }
    return index;
};

---

分析

1. 时间复杂度分析： O(n)
2. 空间复杂度分析：O(1) ? 存疑