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.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (!root){
return 0;
}
if (!root->left && !root->right){
return 1;
}
if (root->left && !root->right){
return minDepth(root->left) + 1;
}
if (root->right && !root->left){
return minDepth(root->right) + 1;
}
return min(minDepth(root->left) + 1, minDepth(root->right) + 1);
}
};
But....
You know the above algorithm is not the optimical. Pre-order complexity is O(n).
we can find more effective algorithm using BFS on complexity O(k) k is the minimun depth of tree
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct Node{
TreeNode * p;
int layer;
Node(TreeNode * p, int layer){
this->p = p;
this->layer = layer;
}
};
int minDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (!root){
return 0;
}
queue<Node > q;
q.push(Node(root,1));
while(!q.empty()){
Node node = q.front();
q.pop();
if (!node.p->left && !node.p->right){
return node.layer;
}
if (node.p->left){
q.push(Node(node.p->left,node.layer+1));
}
if (node.p->right){
q.push(Node(node.p->right,node.layer+1));
}
}
}
};
原文链接: https://www.cnblogs.com/kwill/archive/2013/02/14/2911077.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/77953
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!