面试题28：对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

二叉树的镜像定义：

源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

知识点

二叉树

Qiang的思路

对于这道题来说，如果自己的思路被作者的说法所引导了，那么就是先去求出给定二叉树的镜像二叉树，然后判断两个树是不是相等的。但是，这样做显得太笨了。

对于一个二叉树，如果他是对称的，那么在这个树的对称的节点的值应该是相等的。我们按照这个思路去遍历这个二叉树，问题就出现了，二叉树中一个节点的对称节点如何去找呢？

我们举个例子，根节点的左孩子的对称节点就是根节点的右孩子，左孩子的左孩子的对称点就是右孩子的右孩子，左孩子的右孩子节点的对称点就是右孩子的左孩子节点。以此类推，一个二叉树中一个节点的对称节点就是按照从根到该节点的路径每一步取相反方向得到的节点。

这个思路具体怎么实现呢？我们可以这样想，如果现在已经有一个节点a以及其对称节点b了，a的左孩子的对称节点就是b的右孩子节点，a的右孩子节点就是b的左孩子节点。OK，这就是实现的关键点，因为我们知道根节点的左孩子和右孩子是一对对称节点，那么根据他们两个就可以得到另外的两对对称节点，递归下去就能找到所有的对称节点了。于是乎，代码就出来了。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getResult(self, left, right):
        if left==None or right==None:
            if left==right:
                return True
            return False
        if left.val!=right.val:
            return False
        result1=self.getResult(left.left, right.right)
        result2=self.getResult(left.right, right.left)
        if result1==True and result2==True:
            return True
        return False
        
    def isSymmetrical(self, pRoot):
        # write code here
        if pRoot==None:
            return True
        return self.getResult(pRoot.left, pRoot.right)

Book上的思路

书中说的是通过比较二叉树的前序遍历序列和对称前序遍历序列来判断二叉树是不是对称的。但是通过分析其代码可以看出，代码的具体实现和我的其实是一样的。但是解释的角度不同。

在此，我并不认为书上的解释更好一些，因为书中说的是通过比较前序遍历序列来判断是不是对称的，但是实际代码并不是这样做的。虽然书中的代码可以达到前序遍历的效果，但是却依赖了同时向左和向右（或者是向右和向左）进行比较，也就是说依赖了这样写的代码格式。如果真的先求出先序遍历序列和对称先序遍历序列，然后在判断是不是相等，根据相同与否得到是不是对称二叉树，这样的结果恐怕不是正确的，因为不同的二叉树可能对应的先序遍历结果相同，然而他们之间并不是对称的关系。举个例子：

二叉树 
            1
           / 
          2 
         / 
        3 
镜像二叉树
            1
              \
               2
                \
                 3

两个二叉树的先序遍历结果都是[1,2,3]，但是并不能说第一个二叉树就是对称二叉树。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。