[!info] related notes 算法面试题型 MOC 二叉树高频题

二叉树的最大深度

题目

104. 二叉树的最大深度 - 力扣（LeetCode）

最大深度是根到最远叶子的路径节点数：空树为 0，单节点为 1，不是边数。下面两种独立写法都访问全部节点，时间 O(n)、递归栈 O(h)，退化树可能触发调用栈限制。

题解

链表-二叉树-回溯

var maxDepth = function(root) {
    let ans = 0;
    function dfs(node, depth) {
        if (node === null) {
            return;
        }
        depth++;
        ans = Math.max(ans, depth);
        dfs(node.left, depth);
        dfs(node.right, depth);
    };
    dfs(root, 0);
    return ans;
};

链表-二叉树-回溯

var maxDepth = function(root) {
    if (root === null) {
        return 0;
    }
    const lDepth = maxDepth(root.left);
    const rDepth = maxDepth(root.right);
    return Math.max(lDepth, rDepth) + 1;
};