题目链接：https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/

1. 题目介绍（28. 对称的二叉树）

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

【测试用例】：
示例 1：

输入： root = [1,2,2,3,4,4,3]
输出： true

示例 2：

输入： root = [1,2,2,null,3,null,3]
输出： false

【条件约束】：

限制：
0 <= 节点个数 <= 1000

【相关题目】：

注意：本题与主站 101. 对称二叉树 题目相同。

• 可参考：【LeetCode】No.101. Symmetric Tree – Java Version

2. 题解

2.1 递归（原书题解）-- O(n)

时间复杂度O(n)，空间复杂度O(n)

解题思路：

• 该题相对简单，判断二叉树是否对称，一个很明显的思路就是实现对称的遍历方式。例如，如果采用的是前序遍历，其为根左右，那么我们就实现一个对称前序遍历，根右左，最后比较两个遍历的结果是否一致即可。
• 那么该题就可以简化为，通过递归对其进行逐个遍历，并判断其左、右子树是否对称即可。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {// 使用递归进行求解public boolean isSymmetric(TreeNode root) {return isSymmetric(root,root);}public boolean isSymmetric(TreeNode node1, TreeNode node2){// 递归终止条件：// 1. A树和B树当前节点均为空，说明所有的都判断完毕，符合条件，返回true;// 2. A树和B树当前节点有一个为空，说明此时不相等，返回false;// 3. A树和B树当前节点值不同，返回false.if (node1 == null && node2 == null) return true;if (node1 == null || node2 == null) return false;if (node1.val != node2.val) return false;// 开始向下递归return isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);}
}

2.2 辅助栈（非递归） – O(n)

时间复杂度O(n)，空间复杂度O(n)

该题姐的解题思想就是将root的左右子树逐一压入栈，然后弹出，对比该值是否相等，不相等就返回false，然后依次循环遍历所有子树。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) return true;Stack stack = new Stack<>();stack.push(root.left);stack.push(root.right);while (!stack.empty()) {TreeNode n1 = stack.pop(), n2 = stack.pop();if (n1 == null && n2 == null) continue;if (n1 == null || n2 == null || n1.val != n2.val) return false;stack.push(n1.left);stack.push(n2.right);stack.push(n1.right);stack.push(n2.left);}return true;}
}

3. 参考资料

[1] 面试题28. 对称的二叉树（递归，清晰图解）-- 2.1 图片来源