Comment on page
101.Symmetric Tree
101.Symmetric Tree
难度:Easy
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
递归： 通过一个函数判断，左子树的右孩子和右子树的左孩子，左子树的左孩子和右子树的右孩子应该相等。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
bool check(TreeNode* left , TreeNode* right)
{
if(!left && !right)return true;
else if( !left || !right) return false;
if(left->val != right->val) return false;
return check(left->right, right->left) && check(left->left, right->right);
}
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
if(!root->left && !root->right) return true;
return check(root->left, root->right);
}
};
执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户 内存消耗 :14.7MB, 在所有 C++ 提交中击败了88.35%的用户
迭代： 创建一个队列来保存二叉树的每个节点，然后比较左节点的右孩子和右节点的左孩子。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
if(!root->left && !root->right) return true;
deque<TreeNode*> t;
t.push_back(root);
t.push_back(root);
while(!t.empty())
{
if(!t[0] &&!t[1])
{
t.pop_front();
t.pop_front();
continue;
}
if(!t[0] || !t[1]) return false;
if(t[0]->val != t[1]->val) return false;
t.push_back(t[0]->left);
t.push_back(t[1]->right);
t.push_back(t[0]->right);
t.push_back(t[1]->left);
t.pop_front();
t.pop_front();
}
return true;
}
};
执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户 内存消耗 :14.9MB, 在所有 C++ 提交中击败了79.96%的用户