leetcode刷题：对称二叉树

题目：

给你一个二叉树的根节点 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 个节点；
• 空间复杂度是 O($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$)，空间复杂度是 O($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）则是一种从图的某一节点（源节点）出发，尽可能深地访问图中的节点，当达到图的某个叶节点时，再返回上一级节点继续搜索，直到访问完所有节点为止的遍历方法。这种遍历方式类似于树的先序遍历。

两种遍历方式各有特点，适用于不同的应用场景。广度优先遍历通常用于寻找从源节点到目标节点的最短路径，而深度优先遍历则常用于图的连通性判断、生成树的构建等任务。