# 「力扣」第 101 题：判断两棵二叉树是否左右对称
# 题目描述
给你一个二叉树的根节点 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
进阶： 你可以运用递归和迭代两种方法解决这个问题吗？
个人看法：这道题没有技巧，递归和非递归解法在初学的时候如果没有想到很正常，写多了就慢慢理解了。其实它们分别对应了「深度优先遍历」和「广度优先遍历」。
# 理解题意
首先理解什么是镜面对称。两个结点的根结点的 值 必须相等，并且：
- 左边的左结点的值等于右边的右结点的值；
- 左边的右结点的值等于右边的左结点的值。
# 方法一：递归
- 递归的做法，其实就是
dfs（深度优先遍历），需要引入辅助函数； - 技巧在于设置辅助函数，画出 3 到 4 层结构图就容易发现递归关系了。特别注意：递归比较的时候，根结点的值一定要相等。
Java 代码：
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode p1, TreeNode p2) {
// 左右都为空，判为相等
if (p1 == null && p2 == null) {
return true;
}
// 走到这里左右之一至少非空，或者都非空，但它们的 val 不等，都不能叫做 symmetric tree
if (p1 == null || p2 == null || p1.val != p2.val) {
return false;
}
// 对称地去比较，p1 的左边和 p2 的右边，p1 的右边和 p2 的左边
return isSymmetric(p1.left, p2.right) && isSymmetric(p1.right, p2.left);
}
}
Python 代码：
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
return self.__helper(root.left, root.right)
def __helper(self, left_node, right_node):
if left_node is None and right_node is None:
return True
if left_node is None or right_node is None or left_node.val != right_node.val:
return False
return self.__helper(left_node.left, right_node.right) and self.__helper(
left_node.right, right_node.left)
# 方法二：非递归
借助双端队列辅助判断。其实就是 bfs（广度优先遍历）。自己画一个图，就好理解了。
Java 代码：
import java.util.LinkedList;
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.addFirst(root.left);
queue.addLast(root.right);
while (!queue.isEmpty()) {
// 出队的时候，看看是否有左右孩子，分别入队
TreeNode leftNode = queue.pollFirst();
TreeNode rightNode = queue.pollLast();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null || rightNode == null) {
return false;
}
queue.addFirst(leftNode.right);
queue.addFirst(leftNode.left);
queue.addLast(rightNode.left);
queue.addLast(rightNode.right);
if (leftNode.val != rightNode.val) {
return false;
}
}
return true;
}
}
Python 代码：
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 先写递归终止条件
if root is None:
return True
# 其实应该用 from collections import deque
deque = []
deque.insert(0, root.left)
deque.append(root.right)
while deque:
l_node = deque.pop(0)
r_node = deque.pop()
if l_node is None and r_node is None:
continue
if l_node is None or r_node is None:
return False
# 代码走到这里一定有 l_node 和 r_node 非空
# 因此可以取出 val 进行判断了
if l_node.val != r_node.val:
return False
deque.insert(0, l_node.right)
deque.insert(0, l_node.left)
deque.append(r_node.left)
deque.append(r_node.right)
return True
# 转换成以前见过的问题（反转二叉树）
说明：这个解法很麻烦，很死板。
之前在刷这道题的时候，写过一个解法：先拷贝一棵二叉树，再反转，将反转以后的二叉树和自己比较，看看是否相等，这个思路就转化成了以前我们解决过的问题。另外复制的时候，我们可以反着复制，然后比较。
Java 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
TreeNode copyBinaryTree = copyBinaryTree(root);
TreeNode invertBinaryTree = invertBinaryTree(copyBinaryTree);
return isSameTree(root, invertBinaryTree);
}
private boolean isSameTree(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null || t1.val != t2.val) {
return false;
}
return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
}
private TreeNode invertBinaryTree(TreeNode node) {
if (node == null) {
return node;
}
invertBinaryTree(node.left);
invertBinaryTree(node.right);
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
return node;
}
// 也使用递归的方式完成（熟悉一下如何完成二叉树的复制）
private TreeNode copyBinaryTree(TreeNode node) {
if (node == null) {
return null;
}
TreeNode newTreeNode = new TreeNode(node.val);
newTreeNode.left = copyBinaryTree(node.left);
newTreeNode.right = copyBinaryTree(node.right);
return newTreeNode;
}
}
作者：liweiwei1419 链接：https://suanfa8.com/tree/solutions/0101-symmetric-tree 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。