給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
說明: 葉子節點是指沒有子節點的節點。
- 示例:
給定二叉樹[3,9,20,null,null,15,7]
3/ \9 20/ \15 7
返回它的最小深度 2.
- c++ 廣度優先
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {std::queue<TreeNode*> nodeQueue;int res = 0;if (root) {if (!root->left && !root->right) {return 1;} else {res++;nodeQueue.push(root);}} else {return 0;}while(!nodeQueue.empty()) {auto nodeQueueSize = nodeQueue.size();for (int i=0; i<nodeQueueSize; i++) {auto node = nodeQueue.front();if (!node->left && !node->right) {return res;} else {if (node->left) {nodeQueue.push(node->left);}if (node->right) {nodeQueue.push(node->right);}}nodeQueue.pop();}res++;}return res;}
};
- c++ 遞歸
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {if (!root) {return 0;}if (!root->left && !root->right) {return 1;}auto min_depth = INT_MAX;if (root->left) {min_depth = min(minDepth(root->left), min_depth);}if (root->right) {min_depth = min(minDepth(root->right), min_depth);}return min_depth + 1;}
};
- Python 遞歸
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0children = [root.left, root.right]if not any(children):return 1min_depth = float('inf')for c in children:if (c):min_depth = min(self.minDepth(c), min_depth)return min_depth + 1
來源：力扣（LeetCode）
