28.md

对称的二叉树

题目

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

要求：空间复杂度 O(n)，时间复杂度 O(n)

备注：你可以用递归和迭代两种方法解决这个问题

示例

输入：{1,2,2,3,4,4,3}

返回值：true

思路

• 以根节点为准生成两个副本递归比较
• 递归终止条件：左右节点都为空直接返回true，否则，如果只有一个为空返回false
• 对于相同位置的节点，【值相同】且【a的左枝等于b的右枝】且【a的右枝等于b的左枝】时是对称的

实现

func isSymmetrical(pRoot *TreeNode) bool {
	return isSame(pRoot, pRoot)
}

func isSame(root1 *TreeNode, root2 *TreeNode) bool {
	if root1 == nil && root2 == nil {
		return true
	}
	if root1 == nil || root2 == nil {
		return false
	}
	return root1.Val == root2.Val &&
		isSame(root1.Left, root2.Right) &&
		isSame(root1.Right, root2.Left)
}