题解 | #二叉树的最大深度#

/**
 * 解法一：递归
 * 思路：
 * （1）最大深度是所有叶子节点的深度的最大值，深度是指树的根节点到任一-叶子节点路径上节点的数量，
 * （2）因此从根节点每次往下一层深度就会加1。
 * （3）因此二叉树的深度就等于根结点这个1层加上左子树和右子树深度的最大值
 * 时间复杂度: O(n)，其中n为二叉树的节点数，遍历整棵二叉树
 * 空间复杂度: O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n
 */
export function maxDepth(root: TreeNode | null): number {
    if (root == null) return 0
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

/**
 * 解法二：层次遍历
 * 思路：
 *   既然是统计二叉树的最大深度，除了根据路径到达从根节点到达最远的叶子节点以外，我
 *   们还可以分层统计。对于一棵二叉树而言，必然是一层一层的，那一层就是一个深度，有
 *   的层可能会很多节点，有的层如根节点或者最远的叶子节点，只有一个节点，但是不管多
 *   少个节点，它们都是一层。因此我们可以使用层次遍历，二叉树的层次遍历就是从上到下
 *   按层遍历，每层从左到右，我们只要每层统计层数即是深度。
 * 时间复杂度: O(n)，其中n为二叉树的节点数，遍历整棵二叉树
 * 空间复杂度: O(n)，辅助队列的空间最坏为n
 */
export function maxDepth(root: TreeNode | null): number {
    if(root == null) return 0

    const queue: TreeNode[] = []
    queue.push(root)
    let maxDep = 0

    while (!queue.length) {
        for (let i = 0; i < queue.length; i++) {
            const node = queue.shift()
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
        maxDep++
    }

    return maxDep
};

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview