算法设计

剑指offer之058-对称的二叉树

作者明柳梦少，发布于 。

题目描述

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

思路

思路1. 正常的层序遍历

思路2. 两种中序遍历

  1. 左->根->右
  2. 右->根->左
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def isEqual(p1, p2):
    if not p1 and not p2:
        return True
    elif p1 and p2 and p1.val == p2.val:
        return True
    else:
        return False

class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot: return True
        queue = [pRoot]
        while queue:
            n = len(queue)
            if queue[0] != pRoot and n % 2 != 0: 
                return False
            for i in range(n//2):
                if not isEqual(queue[i], queue[-1-i]):
                    return False
            for _ in range(n):
                node = queue.pop(0)
                if not node: continue
                queue.append(node.left)
                queue.append(node.right)
        return True
隐藏作者信息

关于明柳梦少

坚守自己的原则，不随波逐流。