欢迎访问LeetCode题解合集
题目描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
[HTML_REMOVED]
[HTML_REMOVED]
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
- 树中节点数的范围在 $[0, 10^5]$ 内
- $-1000 \le Node.val \le 1000$
题解:
法一:
深搜。
相比较普通的求二叉树深度:
int Depth(TreeNode* root) {
if ( !root ) return 0;
int l = minDepth( root->left );
int r = minDepth( root->right );
return max( l, r ) + 1;
}
此题需要注意的是 max -> min
,但只改这个是不行的,比如只有左子树,没有右子树,返回的结果就是 1
。修改如下:
int minDepth(TreeNode* root) {
if ( !root ) return 0;
int l = minDepth( root->left );
int r = minDepth( root->right );
if ( l && r ) return min( l, r ) + 1;
return max( l, r ) + 1;
}
时间复杂度:$O(n)$
额外空间复杂度:$O(logn)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if ( !root ) return 0;
int l = minDepth( root->left );
int r = minDepth( root->right );
if ( l && r ) return min( l, r ) + 1;
return max( l, r ) + 1;
}
};
/*
时间:288ms,击败:94.78%
内存:141.3MB,击败:58.66%
*/
法二:
广搜,搜到的第一个叶子节点一定是深度最小的节点。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if ( !root ) return 0;
queue<TreeNode*> q;
int dep = 0, size, i;
q.push( root );
while ( q.size() ) {
size = q.size();
++dep;
for ( i = 0; i < size; ++i ) {
root = q.front(); q.pop();
if ( !root->left && !root->right ) return dep;
if ( root->left ) q.push( root->left );
if ( root->right ) q.push( root->right );
}
}
return dep;
}
};
/*
时间:296ms,击败:91.07%
内存:141.2MB,击败:73.67%
*/