二叉树心法（后序篇）

652. 寻找重复的子树 https://leetcode.cn/problems/find-duplicate-subtrees

652. Find Duplicate Subtrees https://leetcode.com/problems/find-duplicate-subtrees

Info

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

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

LeetCode	Difficulty
652. Find Duplicate Subtrees	🟠

Prerequisites

Before reading this article, you need to study:

• Basics of Binary Tree Structures
• DFS/BFS Traversal of Binary Trees
• Dong Ge's Guide to Binary Trees (Overview)

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

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

// 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 TreeNodes with values 4 and 2 (it doesn't matter which specific nodes).

loading...