二叉树心法（后序篇）

本文是承接 二叉树心法（纲领篇） 的第四篇文章，主要讲二叉树后序位置的妙用，复述下前文关于后序遍历的描述：

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

多说无益，我们直接看题，这是力扣第 652 题「寻找重复的子树」：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

输入：root = [2,1,1]
输出：[[1]]

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

// 函数签名如下
List<TreeNode> findDuplicateSubtrees(TreeNode root);

// 函数签名如下
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root);

# 函数签名如下
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:

// 函数签名如下
func findDuplicateSubtrees(root *TreeNode) []*TreeNode

// 函数签名如下
var findDuplicateSubtrees = function(root) {}

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

说起来比较绕，举例来说，比如输入如下的二叉树：

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

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

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