LeetCodeの二叉木に関する練習問題のまとめと解法
LeetCode 222:ツリーのノード数を求める完全二叉木が与えられる.
LeetCode 94:ツリーの中順ループ
LeetCode 100:同じツリー
LeetCode 101:対称の二叉木
LeetCode 104:ツリーの最大深さ
LeetCode 111:ツリーの最小深さ
LeetCode 144:ツリーの前順ループ
LeetCode 145:二叉木の後序遍歴
LeetCode 112:パスの合計
， 。
：
： ， ， ， 。 h ， 1~ 2h 。
:
:
1
/ \
2 3
/ \ /
4 5 6
: 6
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL)
{
return 0;
}
return 1+countNodes(root->left)+countNodes(root->right);
}
};
LeetCode 94:ツリーの中順ループ
class Solution
{
private:
struct Command
{
string s;//go print
TreeNode *node;
Command(string s,TreeNode *node):s(s),node(node){
}
};
public:
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> res;
if(root==NULL)
return res;
stack<Command> stack;
stack.push(Command("go",root));
while(!stack.empty())
{
Command command=stack.top();
stack.pop();
if(command.s=="print")
res.push_back(command.node->val);
else
{
assert(command.s=="go");
if(command.node->right)
stack.push(Command("go",command.node->right));
stack.push(Command("print",command.node));
if(command.node->left)
stack.push(Command("go",command.node->left));
}
}
return res;
}
};
LeetCode 100:同じツリー
， 。
， ， 。
1:
: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
: true
2:
: 1 1
/ \
2 2
[1,2], [1,null,2]
: false
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==NULL && q==NULL)
return true;
if(p==NULL || q==NULL)
return false;
if(p->val != q->val)
return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};
LeetCode 101:対称の二叉木
， 。
， [1,2,2,3,4,4,3] 。
1
/ \
2 2
/ \ / \
3 4 4 3
[1,2,2,null,3,null,3] :
1
/ \
2 2
\ \
3 3
class Solution {
public:
bool isSymmetric(TreeNode *root1,TreeNode *root2)
{
if(root1==NULL && root2==NULL) return true;
if(root1==NULL || root2==NULL) return false;
if(root1->val != root2->val) return false;
return isSymmetric(root1->left,root2->right) &&
isSymmetric(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
if(root==NULL)
return true;
return isSymmetric(root->left,root->right);
}
};
LeetCode 104:ツリーの最大深さ
， 。
。
: 。
：
[3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
3
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL)
return 0;
int leftDepth=1;
int rightDepth=1;
if(root->left)
{
leftDepth+=maxDepth(root->left);
}
if(root->right)
{
rightDepth+=maxDepth(root->right);
}
return leftDepth>rightDepth?leftDepth:rightDepth;
}
};
LeetCode 111:ツリーの最小深さ
， 。
。
: 。
:
[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
2.
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==NULL)
{
return 0;
}
int leftDepth=1;
int rightDepth=1;
if(root->left)
{
leftDepth+=minDepth(root->left);
}
if(root->right)
{
rightDepth+=minDepth(root->right);
}
if(leftDepth==1 ) return rightDepth;
if(rightDepth==1) return leftDepth;
return leftDepth>rightDepth?rightDepth:leftDepth;
}
};
LeetCode 144:ツリーの前順ループ
， 。
:
: [1,null,2,3]
1
\
2
/
3
: [1,2,3]
class Solution
{
private:
struct Command
{
string s;//go print
TreeNode *node;
Command(string s,TreeNode *node):s(s),node(node){
}
};
public:
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> res;
if(root==NULL)
return res;
stack<Command> stack;
stack.push(Command("go",root));
while(!stack.empty())
{
Command command=stack.top();
stack.pop();
if(command.s=="print")
res.push_back(command.node->val);
else
{
assert(command.s=="go");
if(command.node->right)
stack.push(Command("go",command.node->right));
if(command.node->left)
stack.push(Command("go",command.node->left));
stack.push(Command("print",command.node));
}
}
return res;
}
};
LeetCode 145:二叉木の後序遍歴
， 。
:
: [1,null,2,3]
1
\
2
/
3
: [3,2,1]
class Solution
{
private:
struct Command
{
string s;//go print
TreeNode *node;
Command(string s,TreeNode *node):s(s),node(node){
}
};
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> res;
if(root==NULL)
return res;
stack<Command> stack;
stack.push(Command("go",root));
while(!stack.empty())
{
Command command=stack.top();
stack.pop();
if(command.s=="print")
res.push_back(command.node->val);
else
{
assert(command.s=="go");
stack.push(Command("print",command.node));
if(command.node->right)
stack.push(Command("go",command.node->right));
if(command.node->left)
stack.push(Command("go",command.node->left));
}
}
return res;
}
};
LeetCode 112:パスの合計
， ， 。
: 。
:
， sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
true, 22 5->4->11->2。
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root==NULL) return false;
if(root->left == NULL && root->right == NULL)
return root->val == sum;
if(hasPathSum(root->left,sum-root->val))
return true;
if(hasPathSum(root->right,sum-root->val))
return true;
return false;
}
};