题目：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解题思路：
方法一：递归
对称二叉树定义： 对于树中任意两个对称节点 L 和 R ，一定有：
L.val = R.val：即此两对称节点值相等。L.left.val = R.right.val：即 LLL 的 左子节点 和 RRR 的 右子节点 对称。L.right.val=R.left.val：即 LLL 的 右子节点 和 RRR 的 左子节点 对称。
根据以上规律，使用深度优先探索（DFS)遍历，考虑从顶至底递归，判断每对左右节点是否对称，从而判断树是否为对称二叉树。
- 算法的时间复杂度是 O( n n n)，因为要遍历 n 个节点；
- 空间复杂度是 O( n n n)，空间复杂度是递归的深度，也就是跟树高度有关，最坏情况下树变成一个链表结构，高度是n。
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if (L == null && R == null) return true;
if (L == null || R == null || L.val != R.val) return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}
}
方法二：迭代
我们通过使用广度优先搜索（BFS）遍历，首先将根节点两次放入队列中，每一次取出两个进行比较，如果是对称二叉树，则它们的连续的两个元素值应该相等。
- 首先从队列中拿出两个节点
left和right比较 - 将
left的left节点和right的right节点放入队列 - 将
left的right节点和right的left节点放入队列
时间复杂度是 O( n n n)，空间复杂度是 O( n n n)。
动画演示如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null || (root.left==null && root.right==null)) {
return true;
}
//用队列保存节点
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
//将根节点的左右孩子放到队列中
queue.add(root.left);
queue.add(root.right);
while(queue.size()>0) {
//从队列中取出两个节点，再比较这两个节点
TreeNode left = queue.removeFirst();
TreeNode right = queue.removeFirst();
//如果两个节点都为空就继续循环，两者有一个为空就返回false
if(left==null && right==null) {
continue;
}
if(left==null || right==null) {
return false;
}
if(left.val!=right.val) {
return false;
}
//将左节点的左孩子， 右节点的右孩子放入队列
queue.add(left.left);
queue.add(right.right);
//将左节点的右孩子，右节点的左孩子放入队列
queue.add(left.right);
queue.add(right.left);
}
return true;
}
}
关于DFS和BFS
广度优先和深度优先是两种常用的图遍历算法。
-
广度优先遍历（Breadth-First Search, BFS）是一种从图的某一节点（源节点）出发，先访问该节点的所有相邻节点，然后对每个相邻节点再访问它们的相邻节点，如此层层推进，直到访问完所有节点为止的遍历方法。这种遍历方式类似于树的层次遍历。
-
深度优先遍历（Depth-First Search, DFS）则是一种从图的某一节点（源节点）出发，尽可能深地访问图中的节点，当达到图的某个叶节点时，再返回上一级节点继续搜索，直到访问完所有节点为止的遍历方法。这种遍历方式类似于树的先序遍历。
两种遍历方式各有特点，适用于不同的应用场景。广度优先遍历通常用于寻找从源节点到目标节点的最短路径，而深度优先遍历则常用于图的连通性判断、生成树的构建等任务。
