题解 | #对称的二叉树#

使用中序遍历，如果是对称的，遍历结果一定是对称的，且结点个数一定是奇数个，再排除根结点下左右子树值不相等的情况即可

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        #空树对称
        if not pRoot:
            return True
        #有左右结点，但结点值不同，一定不对称
        if pRoot.left and pRoot.right:
            if pRoot.left.val != pRoot.right.val:
                return False   
        #非递归中序遍历
        stack = []
        res = []
        p = pRoot
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            if not p:
                p = stack.pop()
                res.append(p.val)
                p = p.right
        n = len(res)
        #偶数个结点一定不对称
        if n%2 == 0:
            return False
        #看看中序遍历结果对不对称
        for i in range(int(n/2)):
            if res[i] != res[-1-i]:
                return False
        return True