Question :
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.
Anwser 1 :
/**
* 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 == NULL) return 0;
int left = minDepth(root->left) + 1;
int right = minDepth(root->right) + 1;
// leaf
if (left == 1 || right == 1)
return left > right ? left : right;
return left < right ? left : right;
}
};
Anwser 2 :
/**
* 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 == NULL) return 0;
int depth = 1;
queue <TreeNode *> current;
queue <TreeNode *> next;
current.push(root);
while (!current.empty())
{
while (!current.empty())
{
TreeNode *n = current.front();
current.pop();
if (n->left==NULL && n->right == NULL) return depth;
if (n->left) next.push(n->left);
if (n->right) next.push(n->right);
}
queue <TreeNode *> t; // init queue
current = next;
next = t;
depth += 1;
}
return depth;
}
};