Problem
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 binary tree [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
return its minimum depth = 2.
Solution: Recursion
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua, 4 ms class Solution { public: int minDepth(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; int l = root->left ? minDepth(root->left) : INT_MAX; int r = root->right ? minDepth(root->right) : INT_MAX; return min(l, r) + 1; } }; |
Python3
1 2 3 4 5 6 7 8 9 |
class Solution: def minDepth(self, root): if not root: return 0 if not root.left and not root.right: return 1 l = self.minDepth(root.left) r = self.minDepth(root.right) if not root.left: return 1 + r if not root.right: return 1 + l return 1 + min(l, r) |
Related Problem
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment