Minimum Depth of Binary Tree#

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.

Example#

Given the binary tree [3,9,20,null,null,15,7].

Solution#

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0;
    if(root.left === null && root.right !== null) return minDepth(root.right) + 1;
    if(root.right === null && root.left !== null) return minDepth(root.left) + 1;
    var lh = minDepth(root.left);
    var rh = minDepth(root.right);
    return Math.min(lh, rh) + 1;
};

Idea#

Use the depth-first search method to traverse the entire tree, compare the minimum height subtree, and return the height of the subtree with the minimum height. For each non-leaf node, only need to calculate the minimum leaf node depth of its left and right subtrees. Note that the minimum depth defined in the question is the number of nodes along the shortest path from the root node to the nearest leaf node, and the leaf node is a node with no children. Therefore, the minimum depth of a binary tree with two nodes is 2. First, if the node is not defined, then its height is considered as 0 and returned as 0. For the requirement in the question that the minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node, when the left subtree does not exist and the right subtree exists, return the minimum depth of the right subtree +1. If the left subtree exists and the right subtree does not exist, return the minimum depth of the left subtree +1. Then get the minimum depth of the left subtree and the right subtree, compare the two, and return the depth of the smaller subtree +1.

Daily Topic#

Reference#