手把手带你刷二叉树（三期）

按着前两篇文章的思路，接下来我们应该思考一个问题：

如何判断我们应该用前序还是中序还是后序遍历的框架？ 那么本文就针对这个问题，用一个例子来讲清楚， 根据题意，思考一个二叉树节点需要做什么，到底用什么遍历顺序就清楚了。

寻找重复子树

这是 LeetCode 第 652 题：寻找重复子树 (opens new window)

我来简单解释一下题目，输入的是一棵二叉树的根节点 root，返回的是一个列表，里面装着若干个二叉树节点，这些节点对应的子树在原二叉树中是重复存在的。

举个例子来说，比如输入如下二叉树：

首先节点 4 本身可以作为一棵子树，且二叉树中有多个节点 4:

类似的，还存在着两棵以 2 为根的重复子树：

那么我们返回的列表中就应该有两个 TreeNode，值分别为 4 和 2（具体是哪个节点无所谓）。

这种题目该怎么做呢？ 还是老套路，先思考，对于某个节点，它应该做什么。

比如你站在图中这个 节点 2 上：

如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？

你需要知道以下两点：

• 以我为根的这棵二叉树（子树）长啥样？
• 以其他节点为根的子树都长啥样

这叫知己知彼，我得知道自己是啥样，还有别人是啥样，才能知道有没有人和自己重复。

以我为根的二叉树长啥样

其实看到这个问题就可以判断本题要用「后序遍历」框架来解决：

function traverse(root: TreeNode): void {
  traverse(root.left)
  traverse(root.right)
  // 解法代码位置
}

为什么？因为我们要知道以自己为根的子树长啥样，是不是得先知道左右子树长啥样，再加上自己就构成了一棵完整的子树，综上这不就是一个「后序遍历」框架吗。

我们都知道，在 JS 中的不同的引用变量即使长得一模一样，它们之间也是不相等的，因此我们需要将引用变量转换成基本变量，这就是「二叉树的序列化与反序列化」。

所以，我们可以通过拼接字符串的方式把二叉树序列化：

function traverse(root: TreeNode): string {
  // 对于空节点，我们可以用一个特殊的字符串来表示
  if(!root) return '#'
  
  // 将左右子树序列化成字符串
  const left = traverse(root.left)
  const right = traverse(root.right)
  // 后序遍历代码位置
  // 左右子树加上自己就是以自己为根的二叉树序列化结果
  const subTree = `${left},${right},${root.val}`
  return subTree
}

这样，我们第一个问题就解决了，对于每个节点，递归函数中的 subTree 变量就可以描述以该节点为根的二叉树。

以其他节点为根的二叉树长啥样

非常简单，我们只需要把每一次序列化之后的结果 memo 起来，然后在通过判断是否有相同的，即可判断出是否有重复：

function findDuplicateSubtrees(root: TreeNode): TreeNode[] {
  const memo = new Map<string, number>()
  const res: TreeNode[] = []
  
  function traverse(root: TreeNode | null): string {
    if(!root) return '#'
    
    const left = traverse(root.left)
    const right = traverse(root.right)
    
    const subTree = `${left},${right},${root.val}`
    const count = memo.get(subTree) || 0
    if (count === 1) {
      res.push(root)
    }
    memo.set(subTree, count + 1)

    return subTree
  }
  
  traverse(root)
  
  return res
}