题目在这:https://leetcode-cn.com/problems/symmetric-tree/
法一:
思路分析:
题目没什么难的。对称二叉树，也可以理解为镜像二叉树。
第一种方法比较容易理解，对称二叉树有个性质，就是前序遍历等于后序遍历的倒叙。
有个这个性质，算法就容易出来了。
先先序遍历一遍，存列表里，
然后后序遍历一遍，存列表里，
翻转其中一个列表，比较一下看是不是一样就可以啦~。
不过这里有一个注意的点，就是当出现None的时候。也要加到列表里。
防止数值相同结构不同的树。
还有三种情况提前排除。
一种是空。什么也没有。直接返回false。
一种是空树，只有根节点，必然对称。返回true。
还有一种就是有根节点，但左和右子树只有一边，必然不对称。返回false。
def isSymmetric(self, root: TreeNode) -> bool:
a = root # 指向第一个树
b = root # 指向第二个数
res_pre = [] # 存先序遍历
res_aft = [] # 存后序遍历
if root == None:
return False
if root and root.left == None and root.right == None:
return True
if root.left == None or root.right == None:
return False
# 先序遍历
def dfs_pre(a):
if a:
res_pre.append(a.val)
dfs_pre(a.left)
dfs_pre(a.right)
elif a == None:
res_pre.append(None)
dfs_pre(a)
# 后序遍历
def dfs_aft(b):
if b:
dfs_aft(b.left)
dfs_aft(b.right)
res_aft.append(b.val)
elif b == None:
res_aft.append(None)
dfs_aft(b)
# 列表翻转
res_aft.reverse()
if res_aft == res_pre:
return True
else:
return False
法二:
思路分析:
首先来看一张图!
假设左边的树为A树。右边的树为B树。
在这种图里可以看到，哪些元素是对应比较的？
两棵树的根节点。
A树的左子树根节点 和 B树的右子树的根节点。(A.left 和B.right)
A树的左子树的左子树 和 B树的右子树的右子树。(A.left.left和B.right.right)
A树的左子树的右子树 和 B树的右子树的左子树(A.left.right 和B.right.left)
以此类推
由于题目中给的是一棵树。所以我们不需要管根节点，只需要比较根节点的左右子树是否对称就行了。
用left、right分别指向左子树和右子树进行递归。
递归出口和上面的法一是一样的。
完整代码:
def isSymmetric(self, root: TreeNode) -> bool:
if root == None:
return True
return self.dfs(root.left,root.right)
def dfs(self,left,right):
if left == None and right == None:
return True
if left == None or right == None:
return False
if left.val != right.val:
return False
return self.dfs(left.left,right.right) and self.dfs(left.right,right.left)
定义了dfs函数用于递归。且用left、right分别指向左子树和右子树。
最后return的那一小长串，就是找在对称树中该比较的点，具体看我上面的分析。