python-3.x - How to check if tree is symmetric python

Question

For practice, I solved Leetcode 101. Symmetric Tree question:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

I have an idea to do in order traversal, record each node value into list and check the value from the first part, and reverse the second part from the list. But it failed on test case [1,2,3,3,null,2,null] from my local, my value return [3, 2, None, 1, 2, 3, None], but from leetcode it return [3,2,1,2,3] anyone know why and anything wrong with my code?

def isSymmetric(root: 'TreeNode') -> 'bool':

    if not root: return True
    value = []

    def traversal(cur):
        if cur:
            traversal(cur.left)
            value.append(cur.val)
            traversal(cur.right)

    traversal(root)
    size = int(len(value) / 2)
    return value[:size] == value[size + 1:][-1::-1]

标签： python-3.xalgorithmbinary-tree

Answer 1

恐怕中序遍历不能唯一确定一棵树。例如具有结构的树

1
 \
  2
   \
    3

具有相同的中序遍历

  2
 / \
1   3

由于您if cur有条件，因此您的中序遍历将不包括空节点，这使得遍历不唯一。您可以像这样包含空节点：

 def traverse(cur):
     if cur:
         traverse(cur.left)
     values.append(cur.val if cur else None)
     if cur:
         traverse(cur.right)

这将唯一地序列化树节点。

您还可以做的是在这种情况下确定左节点和右节点的结构相同（除了左右颠倒）。这是我接受的解决方案：

class Solution:
    def isSymmetric(self, root: 'TreeNode') -> 'bool':
        if not root:
            return True
        return self.isSymmetricHelper(root.left, root.right)

    def isSymmetricHelper(self, node1, node2):
        if node1 is None and node2 is None:
            return True
        if node1 is None or node2 is None:
            return False
        if node1.val != node2.val: # early stopping - two nodes have different value
            return False 
        out = True
        out = out and self.isSymmetricHelper(node1.left, node2.right)
        if not out: # early stopping
            return False
        out = out and self.isSymmetricHelper(node1.right, node2.left)
        return out

它递归地检查两棵树是否是彼此的镜像（有一些提前停止）。这个想法是如果两棵树是镜像的，则tree1的左子树必须是tree2的右子树的镜像，同样适用于tree1的右子树和tree2的左子树。

虽然两者的运行时间都是 O(n)，但递归方法占用 O(logn) 平均空间（由调用堆栈使用）并且内置提前停止，而您的 serialize-all-nodes 方法占用 O(n) 空间 O (n) 时间。