problem:
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
confused what
"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
Hide Tags Tree Depth-first Search 題意:判斷一棵二叉樹是否為鏡像二叉樹(結構對稱,數字相等)
thinking:
(1)該題合适的解法是遞歸法,采用DFS思想
遞歸,儲存左右兩個節點,然後判斷leftNode->left和rightNode->right,以及leftNode->right和rightNode->left。如此不斷遞歸
(2)還想到另外一種非遞歸法:層序周遊法,子結點為NULL時代表數值0,從左往右層序周遊得到數組a,從右往左層序周遊得到數組b
如果a==b,則該二叉樹是鏡像的。但送出時顯示:Status:
Memory Limit Exceeded
code:
遞歸法:
class Solution {
public:
bool check(TreeNode *leftNode, TreeNode *rightNode)
{
if (leftNode == NULL && rightNode == NULL)
return true;
if (leftNode == NULL || rightNode == NULL)
return false;
return leftNode->val == rightNode->val && check(leftNode->left, rightNode->right) &&
check(leftNode->right, rightNode->left);
}
bool isSymmetric(TreeNode *root) {
if (root == NULL)
return true;
return check(root->left, root->right);
}
};
層序周遊法: Status:
Memory Limit Exceeded
class Solution {
private:
vector<int> res1;
vector<int> res2;
public:
bool isSymmetric(TreeNode *root) {
if(root==NULL)
return true;
res1.clear();
res2.clear();
level_walk_left(root);
level_walk_right(root);
if(res1==res2)
return true;
else
return false;
}
protected:
void level_walk_left(TreeNode *root)
{
queue<TreeNode *> _queue;
_queue.push(root);
while(!_queue.empty())
{
TreeNode *tmp=_queue.front();
if(tmp==NULL)
res1.push_back(0);
else
{
res1.push_back(tmp->val);
_queue.pop();
if(tmp->left!=NULL)
_queue.push(tmp->left);
else
_queue.push(NULL);
if(tmp->right!=NULL)
_queue.push(tmp->right);
else
_queue.push(NULL);
}
}
}
void level_walk_right(TreeNode *root)
{
queue<TreeNode *> _queue;
_queue.push(root);
while(!_queue.empty())
{
TreeNode *tmp=_queue.front();
if(tmp==NULL)
res2.push_back(0);
else
{
res2.push_back(tmp->val);
_queue.pop();
if(tmp->right!=NULL)
_queue.push(tmp->right);
else
_queue.push(NULL);
if(tmp->left!=NULL)
_queue.push(tmp->left);
else
_queue.push(NULL);
}
}
}
};