101.Symmetric Tree
101.Symmetric Tree
难度:Easy
给定一个二叉树,检查它是否是镜像对称的。
1
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
2
3
1
4
/ \
5
2 2
6
/ \ / \
7
3 4 4 3
8
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
9
10
1
11
/ \
12
2 2
13
\ \
14
3 3
15
说明:
16
17
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
Copied!
递归: 通过一个函数判断,左子树的右孩子和右子树的左孩子,左子树的左孩子和右子树的右孩子应该相等。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
bool check(TreeNode* left , TreeNode* right)
12
{
13
14
if(!left && !right)return true;
15
else if( !left || !right) return false;
16
if(left->val != right->val) return false;
17
return check(left->right, right->left) && check(left->left, right->right);
18
19
}
20
public:
21
bool isSymmetric(TreeNode* root) {
22
if(!root) return true;
23
if(!root->left && !root->right) return true;
24
return check(root->left, root->right);
25
26
27
}
28
};
Copied!
执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户 内存消耗 :14.7MB, 在所有 C++ 提交中击败了88.35%的用户
迭代: 创建一个队列来保存二叉树的每个节点,然后比较左节点的右孩子和右节点的左孩子。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
12
public:
13
bool isSymmetric(TreeNode* root) {
14
if(!root) return true;
15
if(!root->left && !root->right) return true;
16
deque<TreeNode*> t;
17
t.push_back(root);
18
t.push_back(root);
19
while(!t.empty())
20
{
21
if(!t[0] &&!t[1])
22
{
23
t.pop_front();
24
t.pop_front();
25
continue;
26
}
27
if(!t[0] || !t[1]) return false;
28
if(t[0]->val != t[1]->val) return false;
29
t.push_back(t[0]->left);
30
t.push_back(t[1]->right);
31
t.push_back(t[0]->right);
32
t.push_back(t[1]->left);
33
t.pop_front();
34
t.pop_front();
35
}
36
return true;
37
38
}
39
};
Copied!
执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户 内存消耗 :14.9MB, 在所有 C++ 提交中击败了79.96%的用户
Copy link