# 剑指 Offer 28. 对称的二叉树
力扣原题链接（点我直达） (opens new window)
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3@阿秀: 代码已成功复制到剪贴板
1
2
3
4
5
2
3
4
5
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3@阿秀: 代码已成功复制到剪贴板
1
2
3
4
5
2
3
4
5
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true@阿秀: 代码已成功复制到剪贴板
1
2
2
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false@阿秀: 代码已成功复制到剪贴板
1
2
2
限制：
0 <= 节点个数 <= 1000@阿秀: 代码已成功复制到剪贴板
1
# 1、递归法
执行用时：12 ms, 在所有 C++ 提交中击败了32.98%的用户
内存消耗：16.3 MB, 在所有 C++ 提交中击败了100.00%的用户
bool isEqual(TreeNode*node1,TreeNode*node2){ if(node1==nullptr && node2 ==nullptr) return true; if(node1==nullptr && node2!=nullptr) return false; if(node2==nullptr && node1!=nullptr) return false; if(node1->val == node2->val) { return isEqual(node1->left,node2->right) && isEqual(node1->right,node2->left); }else return false; } bool isSymmetric(TreeNode* root) { if(root==nullptr) return true; return isEqual(root->left,root->right); }@阿秀: 代码已成功复制到剪贴板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 2、递归法、稍微改进一点
执行用时：8 ms, 在所有 C++ 提交中击败了67.83%的用户
内存消耗：16.4 MB, 在所有 C++ 提交中击败了100.00%的用户
bool isEqual(TreeNode*node1,TreeNode*node2){ if(node1==nullptr && node2 ==nullptr) return true; if(node1 ==nullptr || node2==nullptr) return false;//减少判断 if(node1->val == node2->val) { return isEqual(node1->left,node2->right) && isEqual(node1->right,node2->left); }else return false; } bool isSymmetric(TreeNode* root) { if(root==nullptr) return true; return isEqual(root->left,root->right); }@阿秀: 代码已成功复制到剪贴板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 3、迭代法，借助栈 太麻烦了，不值得借鉴
1 / \ 2 2 \ \ 3 3@阿秀: 代码已成功复制到剪贴板
1
2
3
4
5
6
7
2
3
4
5
6
7
bool isSymmetric(TreeNode* root) { if(!root){ return true; } queue<TreeNode *> que1; que1.push(root); while(!que1.empty()){ int size = que1.size(); vector<TreeNode *> tmp;//判断虽然不是镜像节点，但是值依然相等的情况，比如上述情况 while(size > 0){ TreeNode *fronts = que1.front(); que1.pop(); tmp.push_back(fronts->left); if(fronts->left){ que1.push(fronts->left); } tmp.push_back(fronts->right); if(fronts->right){ que1.push(fronts->right); } size --; } int i=0; int j=tmp.size()-1; while(i<j){ if(tmp[i] != nullptr && tmp[j] != nullptr){ if(tmp[i]->val != tmp[j]->val){ return false; } } else if(tmp[i] == nullptr && tmp[j] == nullptr){ } else{ return false; } i++; j--; } } return true; }@阿秀: 代码已成功复制到剪贴板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41