Binary Tree in Action (Post-order)

This article is the fourth in the series following Essence of Binary Trees (Guideline), focusing on the effective use of post-order positions in binary trees. Let's recap the description of post-order traversal from the previous articles:

In the pre-order position, the code can only obtain data passed from the parent node through function parameters, whereas in the post-order position, the code can access both parameter data and data returned by the subtrees.

In other words, if you notice that a problem is related to subtrees, you likely need to define appropriate function definitions and return values, and write code in the post-order position.

Without further ado, let's look at a problem: 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 have duplicates in the original binary tree.

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

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

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

Therefore, the List we return should contain two TreeNode elements, with values 4 and 2 (the specific nodes do not matter).