# 二叉树心法（后序篇）

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

652. Find Duplicate Subtrees | 🟠 |

Prerequisites

Before reading this article, you need to study:

This article is the fourth in the series following Dong Ge's Guide to Binary Trees (Overview). It mainly discusses the clever use of the post-order position in binary trees. Let's review the description of post-order traversal from the previous articles:

Code in the pre-order position can only get data passed from the parent node through function parameters, while code in the post-order position can get data from both the parameters and the return values passed back by the subtree.

In other words, if you find that a problem involves subtrees, it is highly likely that you need to set a reasonable definition and return value for the function and write code in the post-order position.

Without further ado, let's dive into a problem. Here is LeetCode Problem 652: "Find Duplicate Subtrees":

**652. Find Duplicate Subtrees** | 力扣 | LeetCode |

Given the `root`

of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are **duplicate** if they have the **same structure** with the **same node values**.

**Example 1:**

Input:root = [1,2,3,4,null,2,4,null,null,4]Output:[[2,4],[4]]

**Example 2:**

Input:root = [2,1,1]Output:[[1]]

**Example 3:**

Input:root = [2,2,2,3,null,3,null]Output:[[2,3],[3]]

**Constraints:**

- The number of the nodes in the tree will be in the range
`[1, 5000]`

`-200 <= Node.val <= 200`

```
// function signature as follows
List<TreeNode> findDuplicateSubtrees(TreeNode root);
```

```
// The function signature is as follows
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root);
```

```
# The function signature is as follows
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
```

```
// The function signature is as follows
func findDuplicateSubtrees(root *TreeNode) []*TreeNode
```

```
// The function signature is as follows
var findDuplicateSubtrees = function(root) {}
```

Let me briefly explain the problem. The input is the root node `root`

of a binary tree, and the output is a list containing several binary tree nodes. These nodes correspond to subtrees that are duplicated in the original binary tree.

It might sound a bit complicated, so let's look at an example. Given the following binary tree:

First, the node with value 4 itself can be considered as a subtree, and there are multiple nodes with value 4 in the binary tree:

Similarly, there are two duplicated subtrees with 2 as the root:

Therefore, the `List`

we return should contain two `TreeNode`

s with values 4 and 2 (it doesn't matter which specific nodes).