不确定这个递归是如何工作的

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

递归最好从下往上解开。

非节点（叶节点的女儿）将 return "#".
值为 1 的叶子将 return "##1"（因为它有两个非节点子节点）。
具有两个叶子女儿 1 和 2 的节点 3 将 return ##1##23。 "##1"是左女儿的dfs，"##2"是右女儿的dfs，"3"是字符串化后的当前节点的值。

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

Answer 2

基本上，变量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)
  ...

不确定这个递归是如何工作的

Not sure how this recursion works

python

recursion

binary-tree