11##题目地址
22https://leetcode-cn.com/problems/symmetric-tree/
33
4- ## 思路
4+ > 又是一道“简单题”
55
6- 这是考察二叉树基本操作的经典题目，递归的方式相对好理解一些，迭代法看大家清一色使用队列，其实使用栈也是可以的，只不过遍历的顺序不同而已，关键是要理解只要是对称比较就可以了，遍历的顺序无所谓的。
6+ # 101. 对称二叉树
77
8+ 给定一个二叉树，检查它是否是镜像对称的。
89
9- ### 递归法
10+ < img src = ' ../pics/101. 对称二叉树.png ' width = 600 > </ img ></ div >
1011
11- #### 递归三部曲
12+ #思路
1213
13- * 确定递归函数的参数和返回值
14- * 确定终止条件
15- * 确定单层递归的逻辑
14+ ** 首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！**
1615
17- ##### 确定递归函数的参数和返回值
16+ 对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了 ** 其实我们要比较的是两个树（这两个树是根节点的左右子树） ** ，所以在递归遍历的过程中，也是要同时遍历两棵树。
1817
19- 判断左右孩子是否对称，所以传入的参数为左指针和右指针，那么就返回是否是对称的就可以了，所以返回值是布尔类型。
18+ 那么如果比较呢？
19+
20+ 比较的是两个子树的里侧和外侧的元素是否相等。如图所示：
21+
22+ <img src =' ../pics/101. 对称二叉树1.png ' width =600 > </img ></div >
23+
24+ 那么遍历的顺序应该是什么样的呢？
25+
26+ 本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
27+
28+ ** 正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。**
29+
30+ 但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
31+
32+ 其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。
33+
34+ 说到这大家可能感觉我有点啰嗦，哪有这么多道理，上来就干就完事了。别急，我说的这些在下面的代码讲解中都有身影。
35+
36+ 那么我们先来看看递归法的代码应该怎么写。
37+
38+ ##递归法
39+
40+ ###递归三部曲
41+
42+ 1 . 确定递归函数的参数和返回值
43+
44+ 因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
45+
46+ 返回值自然是bool类型。
2047
2148代码如下：
2249```
2350bool compare(TreeNode* left, TreeNode* right)
2451```
2552
26- ##### 确定终止条件
53+ 2 . 确定终止条件
2754
28- * 左孩子为空，右孩子不为空，不对称，return false
55+ 要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
56+
57+ 节点为空的情况有：（** 注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点** ）
58+
59+ * 左节点为空，右节点不为空，不对称，return false
2960* 左不为空，右为空，不对称 return false
3061* 左右都为空，对称，返回true
62+
63+ 此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
64+
3165* 左右都不为空，比较节点数值，不相同就return false
3266
67+ 此时左右节点不为空，且数值也不相同的情况我们也处理了。
68+
3369代码如下：
3470```
3571if (left == NULL && right != NULL) return false;
3672else if (left != NULL && right == NULL) return false;
37- else if (left == NULL && right == NULL) return true;
38- else if (left->val != right->val) return false;
73+ else if (left == NULL && right == NULL) return true;
74+ else if (left->val != right->val) return false; // 注意这里我没有使用else
3975```
4076
41- #####确定单层递归的逻辑
77+ 注意上面最后一种情况，我没有使用else，而是elseif， 因为我们把以上情况都排除之后，剩下的就是 左右节点都不为空，且数值相同的情况。
78+
79+ 3 . 确定单层递归的逻辑
80+
81+ 此时才进入单层递归的逻辑，单层递归的逻辑就是处理 右节点都不为空，且数值相同的情况。
4282
43- * 比较二叉树外侧是否对称：传入的是左孩子的左指针，右孩子的右指针。
44- * 比较内测是否对称，传入左孩子的右指针，右孩子的左指针。
83+
84+ * 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
85+ * 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
4586* 如果左右都对称就返回true ，有一侧不对称就返回false 。
4687
4788代码如下：
4889
4990```
50- bool outside = compare(left->left, right->right);
51- bool inside = compare(left->right, right->left);
52- return outside && inside;
91+ bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
92+ bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
93+ bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
94+ return isSame;
5395```
5496
55- 这样递归的C++代码就写出来了，如下：
97+ 如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。
98+
99+ 最后递归的C++整体代码如下：
56100
57101```
58102class Solution {
59103public:
60104 bool compare(TreeNode* left, TreeNode* right) {
105+ // 首先排除空节点的情况
61106 if (left == NULL && right != NULL) return false;
62107 else if (left != NULL && right == NULL) return false;
63108 else if (left == NULL && right == NULL) return true;
109+ // 排除了空节点，再排除数值不相同的情况
64110 else if (left->val != right->val) return false;
65- else return compare(left->left, right->right) && compare(left->right, right->left);
111+
112+ // 此时就是：左右节点都不为空，且数值相同的情况
113+ // 此时才做递归，做下一层的判断
114+ bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
115+ bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
116+ bool isSame = outside && inside; // 左子树：中、 右子树：中 （逻辑处理）
117+ return isSame;
66118
67119 }
68120 bool isSymmetric(TreeNode* root) {
@@ -72,46 +124,13 @@ public:
72124};
73125```
74126
75- ### 迭代法
127+ ** 我给出的代码并不简洁，但是把每一步判断的逻辑都清楚的描绘出来了。 **
76128
77- 通过队列来判断二叉树内侧和外侧是否相等，如动画所示：
129+ 如果上来就看网上各种简洁的代码，看起来真的很简单，但是很多逻辑都掩盖掉了，而题解可能也没有把掩盖掉的逻辑说清楚。
78130
79- <video src =' ../video/对称二叉树.mp4 ' controls =' controls ' width =' 640 ' height =' 320 ' autoplay =' autoplay ' > Your browser does not support the video tag.</video ></div >
80-
81- 代码如下：
82-
83- ```
84- class Solution {
85- public:
86- bool isSymmetric(TreeNode* root) {
87- if (root == NULL) return true;
88- queue<TreeNode*> que;
89- que.push(root->left);
90- que.push(root->right);
91- while (!que.empty()) {
92- TreeNode* leftNode = que.front(); que.pop();
93- TreeNode* rightNode = que.front(); que.pop();
94- if (!leftNode && !rightNode) {
95- continue;
96- }
97- if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
98- return false;
99- }
100- que.push(leftNode->left);
101- que.push(rightNode->right);
102- que.push(leftNode->right);
103- que.push(rightNode->left);
104- }
105- return true;
106- }
107- };
108- ```
109- 其实使用栈也是可以的，只要把队列原封不动的改成栈就可以了，我下面也给出了代码。
110-
111- ##C++代码
112-
113- ###递归
131+ ** 盲目的照着抄，结果就是：发现这是一道“简单题”，稀里糊涂的就过了，但是真正的每一步判断逻辑未必想到清楚。**
114132
133+ 当然我可以把如上代码整理如下：
115134```
116135class Solution {
117136public:
@@ -130,46 +149,68 @@ public:
130149};
131150```
132151
133- ###迭代
152+ ** 这个代码就很简洁了，但隐藏了很多逻辑，条理不清晰，而且递归三部曲，在这里完全体现不出来。**
153+
154+ ** 所以建议大家做题的时候，一定要想清楚逻辑，每一步做什么。把道题目所有情况想到位，相应的代码写出来之后，再去追求简洁代码的效果。**
155+
156+ ##迭代法
157+
158+ 这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。
159+
160+ 这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（** 注意这不是层序遍历** ）
134161
135- 使用队列
162+ ###使用队列
163+
164+ 通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，如动画所示：
165+
166+ <img src =' ../video/101.对称二叉树.gif ' width =600 > </img ></div >
167+
168+
169+ 如下的条件判断和递归的逻辑是一样的。
170+
171+ 代码如下：
136172
137173```
138174class Solution {
139175public:
140176 bool isSymmetric(TreeNode* root) {
141177 if (root == NULL) return true;
142178 queue<TreeNode*> que;
143- que.push(root->left);
144- que.push(root->right);
145- while (!que.empty()) {
146- TreeNode* leftNode = que.front(); que.pop();
179+ que.push(root->left); // 将左子树头结点加入队列
180+ que.push(root->right); // 将右子树头结点加入队列
181+ while (!que.empty()) { // 接下来就要判断这这两个树是否相互翻转
182+ TreeNode* leftNode = que.front(); que.pop();
147183 TreeNode* rightNode = que.front(); que.pop();
148- if (!leftNode && !rightNode) {
184+ if (!leftNode && !rightNode) { // 左节点为空、右节点为空，此时说明是对称的
149185 continue;
150186 }
151- if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
187+
188+ // 左右一个节点不为空，或者都不为空但数值不相同，返回false
189+ if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
152190 return false;
153191 }
154- que.push(leftNode->left);
155- que.push(rightNode->right);
156- que.push(leftNode->right);
157- que.push(rightNode->left);
192+ que.push(leftNode->left); // 加入左节点左孩子
193+ que.push(rightNode->right); // 加入右节点右孩子
194+ que.push(leftNode->right); // 加入左节点右孩子
195+ que.push(rightNode->left); // 加入右节点左孩子
158196 }
159197 return true;
160198 }
161199};
162-
163200```
164201
165- 使用栈
202+ ###使用栈
203+
204+ 细心的话，其实可以发现，这个迭代法，其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。
205+
206+ 只要把队列原封不动的改成栈就可以了，我下面也给出了代码。
166207
167208```
168209class Solution {
169210public:
170211 bool isSymmetric(TreeNode* root) {
171212 if (root == NULL) return true;
172- stack<TreeNode*> st;
213+ stack<TreeNode*> st; // 这里改成了栈
173214 st.push(root->left);
174215 st.push(root->right);
175216 while (!st.empty()) {
@@ -191,5 +232,15 @@ public:
191232};
192233```
193234
235+ #总结
236+
237+ 这次我们又深度剖析了一道二叉树的“简单题”，大家会发现，真正的把题目搞清楚其实并不简单，leetcode上accept了和真正掌握了还是有距离的。
238+
239+ 我们介绍了递归法和迭代法，递归依然通过递归三部曲来解决了这道题目，如果只看精简的代码根本看不出来递归三部曲是如果解题的。
240+
241+ 在迭代法中我们使用了队列，需要注意的是这不是层序遍历，而且仅仅通过一个容器来成对的存放我们要比较的元素，知道这一本质之后就发现，用队列，用栈，甚至用数组，都是可以的。
242+
243+ 如果已经做过这道题目的同学，读完文章可以再去看看这道题目，思考一下，会有不一样的发现！
244+
194245
195246> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。