104. 二叉树的最大深度

[Geekhyt]

原题链接

DFS 深度优先搜索

树的深度 = 左右子树的最大深度 + 1

const maxDepth = function(root) {
    if (!root) { // 递归终止条件
        return 0
    } else {
        const left = maxDepth(root.left)
        const right = maxDepth(root.right)
        return Math.max(left, right) + 1
    }
};

• 时间复杂度: O(n)
• 最坏空间复杂度: O(height), height 表示二叉树的高度

BFS 广度优先搜索

层序遍历时记录树的深度。

二叉树的层序遍历可参考轻松拿下二叉树的层序遍历

const maxDepth = function(root) {
    let depth = 0
    if (root === null) {
        return depth
    }
    const queue = [root]
    while (queue.length) {
        let len = queue.length
        while (len--) {
            const cur = queue.shift()
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
        }
        depth++
    }
    return depth
};

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