題目：

請實(shí)現(xiàn)一個(gè)函數(shù)，用來判斷一棵二叉樹是不是對稱的民泵。如果一棵二叉樹和它的鏡像一樣癣丧，那么它是對稱的。例如栈妆，下圖所示的3棵二叉樹中坎缭，第一棵二叉樹是對稱的，而另外兩棵不是签钩。

思路：

通常我們有3種不同的二叉樹遍歷算法掏呼，即前序遍歷、中序遍歷和后序遍歷铅檩。在這3種遍歷算法中憎夷，都是先遍歷左子節(jié)點(diǎn)再遍歷右子節(jié)點(diǎn)。我們是否可以定義一種遍歷算法昧旨，先遍歷右子節(jié)點(diǎn)再遍歷左子節(jié)點(diǎn)拾给？比如我們針對前序遍歷定義一種對稱的遍歷算法，即先遍歷父節(jié)點(diǎn)兔沃，再遍歷它的右子節(jié)點(diǎn)蒋得，最后遍歷它的左子節(jié)點(diǎn)。

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

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

第三棵二叉樹有些特殊，它所有節(jié)點(diǎn)的值都是一樣的斧账。它的前序遍歷序列是{7, 7, 7, 7, 7, 7}谴返，前序遍歷的對稱遍歷序列也是{7, 7, 7, 7, 7, 7}。這兩個(gè)序列也是一樣的咧织，可顯然第三棵二叉樹不是對稱的嗓袱。怎樣才能正確判斷這種類型的二叉樹呢？只要我們在遍歷二叉樹時(shí)把遇到的null指針也考慮進(jìn)來就行拯爽。

比如第三棵二叉樹的前序遍歷序列在考慮null指針之后為{7, 7, 7, null, null, 7, null, null, 7, 7, null, null, null}索抓。序列的前面3個(gè)7對應(yīng)的是從根節(jié)點(diǎn)開始沿著指向左子節(jié)點(diǎn)的指針遍歷經(jīng)過的3個(gè)節(jié)點(diǎn)，接下來兩個(gè)null指針對應(yīng)的是第三層第一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)毯炮。而前序遍歷的對稱遍歷序列為{7, 7, null, 7, null, null, 7, 7, null, null, 7, null, null}逼肯。這兩個(gè)序列從第三步開始就不一致了。

綜上桃煎，我們可以通過比較二叉樹的前序遍歷序列和對稱前序遍歷序列來判斷二叉樹是不是對稱的篮幢。如果兩個(gè)序列是一樣的，那么二叉樹就是對稱的为迈。

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)注“咋家”