python - Leetcode同一棵树

Question

我正在尝试用 python 解决 leetcode 中的同一棵树。 原来的问题。 https://leetcode.com/problems/same-tree/

我的代码能够通过一些测试用例，但不是全部。无法通过提交。我的想法是展平树并比较两个列表。失败的案例位于代码底部。

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

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        def flatten(root):
            if root is None:
                return ["null"]
            if root.left is None and root.right is None:
                return [root.val]
            if root.left is None:
                # print 'left', [root.val, "null", flatten(root.right)]
                return [root.val, "null", flatten(root.right)]
            if root.right is None:
                # print 'right', [root.val, flatten(root.left), "null"]
                return [root.val, flatten(root.left), "null"]
            else: 
                # print flatten(root.right) + flatten(root.right)
                return flatten(root.right) + flatten(root.right)

        return flatten(p) == flatten(q)



## Failed test case
## [390,255,2266,-273,337,1105,3440,-425,4113,null,null,600,1355,3241,4731,-488,-367,16,null,565,780,1311,1755,3075,3392,4725,4817,null,null,null,null,-187,152,395,null,728,977,1270,null,1611,1786,2991,3175,3286,null,164,null,null,4864,-252,-95,82,null,391,469,638,769,862,1045,1138,null,1460,1663,null,1838,2891,null,null,null,null,3296,3670,4381,null,4905,null,null,null,-58,null,null,null,null,null,null,null,null,734,null,843,958,null,null,null,1163,1445,1533,null,null,null,2111,2792,null,null,null,3493,3933,4302,4488,null,null,null,null,null,null,819,null,null,null,null,1216,null,null,1522,null,1889,2238,2558,2832,null,3519,3848,4090,4165,null,4404,4630,null,null,null,null,null,null,1885,2018,2199,null,2364,2678,null,null,null,3618,3751,null,4006,null,null,4246,null,null,4554,null,null,null,1936,null,null,null,null,2444,2642,2732,null,null,null,null,null,null,null,4253,null,null,null,null,2393,2461,null,null,null,null,4250,null,null,null,null,2537]

## [390,255,2266,-273,337,1105,3440,-425,4113,null,null,600,1355,3241,4731,-488,-367,16,null,565,780,1311,1755,3075,3392,4725,4817,null,null,null,null,-187,152,395,null,728,977,1270,null,1611,1786,2991,3175,3286,null,164,null,null,4864,-252,-95,82,null,391,469,638,769,862,1045,1138,null,1460,1663,null,1838,2891,null,null,null,null,3296,3670,4381,null,4905,null,null,null,-58,null,null,null,null,null,null,null,null,734,null,843,958,null,null,null,1163,1445,1533,null,null,null,2111,2792,null,null,null,3493,3933,4302,4488,null,null,null,null,null,null,819,null,null,null,null,1216,null,null,1522,null,1889,2238,2558,2832,null,3519,3848,4090,4165,null,4404,4630,null,null,null,null,null,null,1885,2018,2199,null,2364,2678,null,null,null,3618,3751,null,4006,null,null,4246,null,null,4554,null,null,null,1936,null,null,null,null,2444,2642,2732,null,null,null,null,null,null,null,4253,null,null,null,null,2461,2393,null,null,null,null,4250,null,null,null,null,2537]

Answer 1

要确定两棵树是否相同，您需要确定结构是否相同，即同一级别和分支上的节点相等。您可以编写一个递归函数来循环树并创建 Huffman编码，稍后可用于比较节点:

class Solution(object):
   @classmethod
   def tree_paths(cls, _tree:TreeNode, _paths = []):
     yield [_tree.val, _paths]
     if _tree.left is not None:
       yield from cls.tree_paths(_tree.left, _paths+[0])
     if _tree.right is not None:
       yield from cls.tree_paths(_tree.right, _paths+[1])
   def isSameTree(self, p, q):
     if p is None and q is None:
        return True
     if not all([p, q]):
        return False
     _tree1, _tree2 = list(self.__class__.tree_paths(p)), list(self.__class__.tree_paths(q))
     if len(_tree1) != len(_tree2):
       return False
     return all(a == b and all(c ==d for c, d in zip(j, l)) for [a, j], [b, l] in zip(_tree1, _tree2))

<小时/>

为了测试，可以创建与原始 TreeNode 具有相同属性的树:

class TreeNode:
  def __init__(self, **kwargs:dict) -> None:
     self.__dict__ = {i:kwargs.get(i) for i in ['val', 'left', 'right']}

t1 = TreeNode(val=1, left=TreeNode(val=2), right=TreeNode(val=3))
t2 = TreeNode(val=1, left=TreeNode(val=2), right=TreeNode(val=3))
t3 = TreeNode(val=1, left=TreeNode(val=2), right=TreeNode(val=4))
print(Solution().isSameTree(t1, t2))
print(Solution().isSameTree(t1, t3))

输出:

True
False

该答案已在 LeetCode 上成功接受。

编辑:您的代码很接近，但是，必须更改flatten(root.right) + flatten(root.right)，因为您两次查找右子树上节点的路径。此外，您还必须包含传递给 isSameTree 的当前树实例的值。因此，flatten(root.right) + flatten(root.right) 必须变为:

return flatten(root.left)+[root.val]+flatten(root.right)