Binary Tree in Action (Post-order)

This article is the fourth part following Binary Tree Techniques (Summary), mainly discussing the clever use of the postorder position in binary trees. Let's recap the previous description of postorder traversal:

The code at the preorder position can only get data passed from the parent node through function parameters, whereas the code at the postorder position can access both the parameter data and the data returned by the subtree through the function's return value.

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

Enough talk, let's dive into a problem. This 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 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).