leetcode：通过倒立树解决对称树问题

Question

我正在研究leetcode问题 101。对称树：

给定二进制树的root，检查它是否是自身的镜子（即，在其中心周围对称）。

这是我的代码：

# 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

我已经通过此代码通过了195/198的测试用例。它失败的第一个测试案例是：

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

倒置函数的代码反转树。 dfs函数在原始的根树上运行一个内部遍历。然后dfs1在倒立的树上进行内存遍历，它们分别附加到两个列表。然后，我们通过比较两个列表是否相同来返回结果。

Answer 1

如果两棵树具有相同的内顺序，则它们是相同的。例如，这些树都具有相同的内顺序序列，因此在它们上运行dfs的结果将导致相同的输出：

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

解决此问题的一种方法是在遇到无，使深度第一阶预订，而不是订购。

代码上的其他一些说明：

• 左和右在invert函数中未使用。如果事实，它们始终是无，因为invert总是返回none。

• 可惜您有两个DFS函数，只是因为您需要在其他列表中的输出。将该功能变成发电机，以便呼叫者可以在所需的位置收集这些值。

导致此代码：

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