LeetCode(111)Minimum Depth of Binary Tree
タイトルは以下の通りです.
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.
テーマ分析:
興味深い問題だたとえば、
rootが空です.
rootは一意のノードです
rootの左サブツリーが空または右サブツリーが空です
私のコードは次のとおりです.
なんだか論理的によくわからないような気がして、調べてみると、もっとはっきりした
update: 2014-10-06
拡張テーマ:
leetcode 104 Maximum Depth of Binary Tree,タイトルはこちら
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.
テーマ分析:
興味深い問題だたとえば、
rootが空です.
rootは一意のノードです
rootの左サブツリーが空または右サブツリーが空です
私のコードは次のとおりです.
// 90ms
/**
* 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) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(root!=NULL&&root->left!=NULL&&root->right!=NULL){
int l=minDepth(root->left);
int r=minDepth(root->right);
return (l<r?l:r)+1;
}else if(root!=NULL&&root->left==NULL){
return 1+minDepth(root->right);
}else if(root!=NULL&&root->right==NULL){
return 1+minDepth(root->left);
}else{
return 0;
}
}
};
なんだか論理的によくわからないような気がして、調べてみると、もっとはっきりした
/**
* 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;
if (root->left == NULL && root->right == NULL)
return 1;
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
if (leftDepth == 0)
return rightDepth + 1;
else if (rightDepth == 0)
return leftDepth + 1;
else
return min(leftDepth, rightDepth) + 1;
}
};
update: 2014-10-06
class Solution {
public:
int minDepth(TreeNode *root) {
if (root == NULL) return 0;
else if (root -> left == NULL) return 1 + minDepth(root->right);
else if (root -> right == NULL) return 1 + minDepth(root->left);
else {
TreeNode* left_node = root->left;
TreeNode* right_node = root->right;
int left_dep = minDepth(left_node);
int right_dep = minDepth(right_node);
return 1 + ((left_dep < right_dep) ? left_dep:right_dep); // , 。
}
}
};
拡張テーマ:
leetcode 104 Maximum Depth of Binary Tree,タイトルはこちら