I am working on LeetCode problem 101. Symmetric Tree:

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

This is my code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        org_root_list=[]
        
        def dfs(root: Optional[TreeNode]) -> None:
            if not root:
                return
            dfs(root.left)
            org_root_list.append(root.val)
            dfs(root.right)
            
        dfs(root)
        
        def invert(root: Optional[TreeNode]) -> None:
            if not root:
                return
            left, right = invert(root.left), invert(root.right)   # dfs
            root.left, root.right = root.right, root.left

        invert(root)    
        root_list=[]
        
        def dfs1(root: Optional[TreeNode]) -> None:
            if not root:
                return
            dfs1(root.left)
            root_list.append(root.val)
            dfs1(root.right)
            
        dfs1(root)
        return root_list==org_root_list

I have passed 195/198 test cases with this code. The first test case it failed was:

[1,2,2,2,null,2]
Output: True
Expected: False

The code for the invert function inverts the tree. The dfs function runs an inorder traversal on the original root tree. And then dfs1 does an inorder traversal on the inverted tree, and they append to two lists, respectively. Then we return the result by comparing whether the two lists were same.

CodePudding user response：

It is not true that if two trees have the same in-order sequence, they are the same. For instance, these trees all have the same in-order sequence, and so the result of running dfs on them would lead to the same output:

    2               3        1
   / \             /          \
  1   3           2            2
                 /              \
                1                3

One way to solve this, is to also produce a value when encountering None, and to make the depth first order a pre-order instead of an in-order.

Some other remarks on your code:

• left and right are not used in the invert function. If fact, they are always None, because invert always returns None.

• It is a pity that you have two dfs functions, just because you need the output in a different list. Turn that function into a generator, so that the caller can collect those values where they want.

That leads to this code:

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode]): 
            if not root:
                yield None  # extra value for each encountered None
                return
            yield root.val  # pre-order instead of in-order
            yield from dfs(root.left)
            yield from dfs(root.right)
                    
        def invert(root: Optional[TreeNode]) -> None:
            if not root:
                return        
            invert(root.left)
            invert(root.right)
            root.left, root.right = root.right, root.left
            
        org_root_list = list(dfs(root))
        invert(root)
        return list(dfs(root)) == org_root_list