104. Maximum Depth of Binary Tree

Maximum Depth of Binary Tree - LeetCodeLeetCode

time: O(n)

space: O(h)

var maxDepth = function (root) {
    return find(root, 0);
};

function find(node, depth = 0) {
    if (node === null) return depth;
    depth++;
    return Math.max(find(node.left, depth), find(node.right, depth));
}

time: O(n)

space: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    const q = [[root, 0]];

    let max = 0;
    while (q.length > 0) {
        const [node, cnt] = q.shift();
        if (node === null) continue;

        max = Math.max(cnt + 1, max);
        if (node.left !== null) q.push([node.left, cnt + 1]);
        if (node.right !== null) q.push([node.right, cnt + 1]);
    }

    return max;
};

time: O(n)

space: O(h) worst n skewed tree (편향 이진 트리)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

function Track() {
    this.depth = 0;
}
const track = new Track();

var maxDepth = function(root) {
    track.depth = 0;
    findDepth(root, 0);
    return track.depth;
};

function findDepth(node, cnt = 0) {
    if (node === null) {
        track.depth = Math.max(track.depth, cnt);
        return;
    }

    cnt += 1;
    findDepth(node.left, cnt);
    findDepth(node.right, cnt);
}