111. Minimum Depth of Binary Tree
給定一棵二元樹，找到它的最小深度。
最小深度是從根節點到最近的葉節點的最短路徑上的節點數。
注意：葉節點是沒有子節點的節點。
範例：
輸入：root = [3,9,20,null,null,15,7] 輸出：2
Python
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
if not root.left:
return self.minDepth(root.right) + 1
if not root.right:
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
43.24MB, 259ms
C++
#include <algorithm> // For std::min
using namespace std;
class Solution {
public:
int minDepth(TreeNode* root) {
if (!root) {
return 0;
}
// If the node is a leaf
if (!root->left && !root->right) {
return 1;
}
// If the node has no left child, explore the right child
if (!root->left) {
return minDepth(root->right) + 1;
}
// If the node has no right child, explore the left child
if (!root->right) {
return minDepth(root->left) + 1;
}
// If the node has both children, find the minimum depth between the two subtrees
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
};
144.85MB, 179ms
Javascript
/**
* 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 minDepth = function(root) {
if (root === null) {
return 0;
}
// If the node has no children, it is a leaf
if (root.left === null && root.right === null) {
return 1;
}
// If there is no left subtree, only consider the right subtree
if (root.left === null) {
return minDepth(root.right) + 1;
}
// If there is no right subtree, only consider the left subtree
if (root.right === null) {
return minDepth(root.left) + 1;
}
// If both left and right subtrees exist, find the minimum depth of both subtrees
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};
83.92MB, 233ms
