刷题15——面试题28：对称的二叉树

题目：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，下图所示的3棵二叉树中，第一棵二叉树是对称的，而另外两棵不是。

思路：

通常我们有3种不同的二叉树遍历算法，即前序遍历、中序遍历和后序遍历。在这3种遍历算法中，都是先遍历左子节点再遍历右子节点。我们是否可以定义一种遍历算法，先遍历右子节点再遍历左子节点？比如我们针对前序遍历定义一种对称的遍历算法，即先遍历父节点，再遍历它的右子节点，最后遍历它的左子节点。

如果用前序遍历算法遍历上图中的第一棵二叉树，则遍历序列是{8, 6, 5, 7, 6, 7, 5}。如果用我们定义的针对前序遍历的对称遍历算法，则得到的遍历序列是{8, 6, 5, 7, 6, 7, 5}。我们注意到这两个序列是一样的。

上图中第二棵二叉树的前序遍历序列是{8, 6, 5, 7, 9, 7, 5}，而对应的对称前序遍历序列为{8, 9, 5, 7, 6, 7, 5}，在这两个序列中，第二步和第五步是不一样的。

第三棵二叉树有些特殊，它所有节点的值都是一样的。它的前序遍历序列是{7, 7, 7, 7, 7, 7}，前序遍历的对称遍历序列也是{7, 7, 7, 7, 7, 7}。这两个序列也是一样的，可显然第三棵二叉树不是对称的。怎样才能正确判断这种类型的二叉树呢？只要我们在遍历二叉树时把遇到的null指针也考虑进来就行。

比如第三棵二叉树的前序遍历序列在考虑null指针之后为{7, 7, 7, null, null, 7, null, null, 7, 7, null, null, null}。序列的前面3个7对应的是从根节点开始沿着指向左子节点的指针遍历经过的3个节点，接下来两个null指针对应的是第三层第一个节点的两个子节点。而前序遍历的对称遍历序列为{7, 7, null, 7, null, null, 7, 7, null, null, 7, null, null}。这两个序列从第三步开始就不一致了。

综上，我们可以通过比较二叉树的前序遍历序列和对称前序遍历序列来判断二叉树是不是对称的。如果两个序列是一样的，那么二叉树就是对称的。

python代码如下：

class TreeNode:
    def __init__(self, x):
        self.val =x
        self.left =None
        self.right =None
        
class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        return self.recursiveTree(pRoot.left, pRoot.right)
    
    def recursiveTree(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val ==right.val:
            return self.recursiveTree(left.left, right.right) and self.recursiveTree(left.right, right.left)
        return False

java代码如下：

//二叉树结构定义如下
class BinaryTreeNode{
    public int value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;
    
    public BinaryTreeNode(){
        
    }
    
    public BinaryTreeNode(int value){
        this.value =value;
        this.left =null;
        this.right =null;
    }
}

public class Solution{
    public boolean isSymmetric(BinaryTreeNode pRoot){
        if (pRroot ==null){
            return True;
        }
        elde{
            return isSymmetric(pRoot.left, pRoot.right);
        }
    }
    
    private boolean isSymmetric(BinaryTreeNode left, BinaryTreeNode right){
        if(left ==null && right ==null){
            return true;
        }
        if(left ==null || right ==null){
            return fasle;
        }
        if(left.value == right.value){
            return isSymmertric(left.left, right.right) && isSymmetric(left.right, right.left);
        }
        return false;
    }
}

更多精彩，关注“咋家”