題目：

請實現(xiàn)一個函數(shù)，用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對稱的。例如，下圖所示的3棵二叉樹中，第一棵二叉樹是對稱的，而另外兩棵不是。

思路：

通常我們有3種不同的二叉樹遍歷算法，即前序遍歷、中序遍歷和后序遍歷。在這3種遍歷算法中，都是先遍歷左子節(jié)點再遍歷右子節(jié)點。我們是否可以定義一種遍歷算法，先遍歷右子節(jié)點再遍歷左子節(jié)點？比如我們針對前序遍歷定義一種對稱的遍歷算法，即先遍歷父節(jié)點，再遍歷它的右子節(jié)點，最后遍歷它的左子節(jié)點。

如果用前序遍歷算法遍歷上圖中的第一棵二叉樹，則遍歷序列是{8, 6, 5, 7, 6, 7, 5}。如果用我們定義的針對前序遍歷的對稱遍歷算法，則得到的遍歷序列是{8, 6, 5, 7, 6, 7, 5}。我們注意到這兩個序列是一樣的。

上圖中第二棵二叉樹的前序遍歷序列是{8, 6, 5, 7, 9, 7, 5}，而對應(yīng)的對稱前序遍歷序列為{8, 9, 5, 7, 6, 7, 5}，在這兩個序列中，第二步和第五步是不一樣的。

第三棵二叉樹有些特殊，它所有節(jié)點的值都是一樣的。它的前序遍歷序列是{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對應(yīng)的是從根節(jié)點開始沿著指向左子節(jié)點的指針遍歷經(jīng)過的3個節(jié)點，接下來兩個null指針對應(yīng)的是第三層第一個節(jié)點的兩個子節(jié)點。而前序遍歷的對稱遍歷序列為{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代碼如下：

//二叉樹結(jié)構(gòu)定義如下
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;
    }
}

更多精彩，關(guān)注“咋家”