Jianbo Dai's

jz028.对称的二叉树

 
  • Jun 02, 2020

题目链接

注意到，如果一棵树满足题目要求，则其前序遍历序列和其翻转后的前序遍历序列应该是完全相同的。按照这个思想，我们可以依次判断该树与其翻转的树的前序遍历序列值是否一直相等，也就是用常规的前根序遍历和先根后右节点后左节点遍历得到的序列是否相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric1(self, root: TreeNode) -> bool:
        if not root:
            return True
        self.res1, self.res2 = [], []
        self.lefttoright(root)
        self.righttoleft(root)
        return self.res1 == self.res2

    def lefttoright(self, root):
        self.res1.append(root.val)
        if root.left:
            self.lefttoright(root.left)
        else:
            self.res1.append('/')
        if root.right:
            self.lefttoright(root.right)
        else:
            self.res1.append('/')

    def righttoleft(self, root):
        self.res2.append(root.val)
        if root.right:
            self.righttoleft(root.right)
        else:
            self.res2.append('/') 
        if root.left:
            self.righttoleft(root.left)
        else:
            self.res2.append('/')

    def isSymmetric2(self, root: TreeNode) -> bool:
        def recur(L, R):
            if not L and not R: return True
            if not L or not R or L.val != R.val: return False
            return recur(L.left, R.right) and recur(L.right, R.left)
        return recur(root.left, root.right) if root else True

    def isSymmetric3(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.recur(root.left, root.right)

    def recur(self, L, R):
        if not L and not R:
            return True
        if not L or not R or L.val != R.val:
            return False
        return self.recur(L.left, R.right) and self.recur(R.left, L.right)
Search