不确定此递归的工作原理

Question

class Solution: 
def findDuplicateSubtrees(self, root):
self.res = []
self.dic = {}
self.dfs(root)
return self.res
def dfs(self, root):
if not root: return '#'
tree = self.dfs(root.left) + self.dfs(root.right) + str(root.val)
if tree in self.dic and self.dic[tree] == 1:
self.res.append(root)
self.dic[tree] = self.dic.get(tree, 0) + 1
return tree

这是获取给定二叉树的所有重复子树的解决方案。 我不确定tree = self.dfs(root.left) + self.dfs(root.right) + str(root.val)想给什么。

我知道它正在尝试进行后序遍历，但是这部分实际上是如何工作的？

如果任何人都可以遵循此代码，那就太好了。谢谢。

Answer 1

基本上，变量tree可以看作是每个子树的编码字符串。我们使用全局字典self.dic来记忆这些编码的字符串。

举个例子：

A
B      C
D   D  E   B
D  D

按照关卡顺序，二叉树可以描述为[[A], [B, C], [D, D, E, B], [#, #, #, #, #, #, D, D]]，所以我们至少有两个重复的子树作为[[B], [D, D]]和[D]按照代码，我们有

dfs(A)
dfs(B)
dfs(D) *save ##D, return ##D
dfs(D) *find ##D, get one subtree, return ##D
*save ##D##DB, return ##D##DB
dfs(C)
...

Answer 2

递归最好自下而上地解开。

• 非节点(叶节点的子节点(将返回"#"。
• 值为1的叶将返回"##1"(因为它有两个非节点子节点(。
• 具有两个叶子3的节点1和2将返回##1##23。"##1"是左子节点的dfs，"##2"是右子节点的dfs，"3"是字符串化当前节点的值。

这样，假设没有值为23的节点和另一个具有空字符串值的节点，您可以看到如果两个不同的节点产生##1##23，它们就是一个重复的子树。如果使用一些额外的分隔符(例如，该行末尾的分号会产生"##1;##2;3;(，这将更加健壮，这足以使其更具可读性和更少歧义。如果使用列表完成，则更安全(但速度更慢(。