题解 | 【清晰图解】#对称的二叉树#递龟已经秒杀

默认你已经理解题意了哈

递归的难点在于：找到可以递归的点在哪里 为什么很多同学觉得递归一看就会，一写就废。 或者说是自己没有深入思考而无法写出来呢，关键是你对递归理解的不够深。

对这道题： 递归的点怎么找？我从拿到题的第一时间开始想，思路如下：

1. 首先你怎么判断一棵树是不是对称二叉树？ 答案：如果所给根节点，为空，那么是对称的。如果不为空的话，那么当他的左子树与右子树对称的时侯，他是对称

2. 然后那怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树 答案：如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。

仔细读这句话，是不是有点绕？怎么感觉有一个功能A我想实现，但我去实现A的时候又要用到A实现后的功能呢，其实答案原来是本身。

当你思考到这里的时候，递归点已经出现了，递归点：我在尝试判断左树与右树对称的条件时，发现这种情况跟两树的孩子的对称情况是有关系的。

这里，你不必有太多疑问，上手去按思路写代码，伪代码这么写：

函数A（左树，右树）功能是返回是否对称

def 函数A（左树，右树）： 左树节点值等于右树节点值

且 函数A（左树的左子树，右树的右子树），

函数A（左树的右子树，右树的左子树）均为真<br> 

才返回真

写着写着。。。你就发现你写出来了。。。。。。

递归来解

前面我说的，镜像对称是关键，就是左子树和右子树是相等的。

注意这句话，左子树和右子树相等，也就是说递归过程的要比较左子树和右子树的值。

我们把根节点的左子树记做 left，右子树记成 right，然后比较 left 是否等于 right，不等的话就直接返回就可以了。 如果是相当的话，直接比较 left 的左节点和 right 的右节点，然后再比较 left 的右节点和 right 的左节点

比如看下面这两个子树的变化(他们分别是根节点的左子树和右子树)，你能观察到这么一个现象：

左子树 22 的左孩子 == 右子树 22 的右孩子
左子树 22 的右孩子 == 右子树 22 的左孩子

    2         2
   / \       / \
  3   4     4   3
 / \ / \   / \ / \
8  7 6  5 5  6 7  8

根据上面信息可以总结出递归方法的两个条件：

终止条件

1. left 和 right 不等，或者 left 和 right 都为空
   
2. 递归的比较 left，left 和 right.right，然后递归去比较 left，right 和 right.left

演示下

写下代码

//Java这样来写
class Solution {
   public boolean isSymmetric(TreeNode root) {
   	if(root==null) {
   		return true;
   	}
   	//调用递归函数，比较左节点，右节点
   	return dfs(root.left,root.right);
   }
   
   boolean dfs(TreeNode left, TreeNode right) {
   	//递归的终止条件是两个节点都为空
   	//或者两个节点中有一个为空
   	//或者两个节点的值不相等
   	if(left==null && right==null) {
   		return true;
   	}
   	if(left==null || right==null) {
   		return false;
   	}
   	if(left.val!=right.val) {
   		return false;
   	}
   	//再递归的比较 左节点的左孩子 和 右节点的右孩子
   	//以及比较  左节点的右孩子 和 右节点的左孩子
   	return dfs(left.left,right.right) && dfs(left.right,right.left);
   }
}

//python这样来写
class Solution(object):
	def isSymmetric(self, root):
		"""
		:type root: TreeNode
		:rtype: bool
		"""
		if not root:
			return True
		def dfs(left,right):
			# 递归的终止条件是两个节点都为空
			# 或者两个节点中有一个为空
			# 或者两个节点的值不相等
			if not (left or right):
				return True
			if not (left and right):
				return False
			if left.val!=right.val:
				return False
			return dfs(left.left,right.right) and dfs(left.right,right.left)
		# 用递归函数，比较左节点，右节点
		return dfs(root.left,root.right)

时间复杂度好多

• 算法的时间复杂度是 O(n)，因为要遍历 n 个节点

• 空间复杂度也是 O(n)，空间复杂度是递归的深度，也就是跟树高度有关，最坏情况下树变成一个链表结构，高度是n。