The other important thing about binary trees is: how do we decide whether we should use a pre-order or a middle-order or a post-order traversal framework? Again, according to the question, think about what a binary tree node needs to do, exactly what traversal order is clear.
Look, this is the force button 652 “find repeating subtree” :
652. Look for duplicate subtrees
The function signature is as follows:
List<TreeNode> findDuplicateSubtrees(TreeNode root);
Copy the codeTo explain the problem briefly, the input is root, the root node of a binary tree, and the return is a list of several binary tree nodes whose subtrees are duplicated in the original binary tree.
For example, enter the following binary tree:
First, node 4 itself can be a subtree, and there are multiple nodes 4 in the binary tree:
Similarly, there are two repeat subtrees with root 2:
The List we return should have two Treenodes of 4 and 2 (it doesn’t matter which node they are).
So how do we do this? So again, think about what it should do for a given node.
For example, if you stand on node 2 in the diagram:
What do you need to know if a subtree rooted in you is duplicated and should be added to the resulting list?
Here are two things you need to know:
1. What does the binary tree (subtree) with me as root look like?
2. What do subtrees rooted in other nodes look like?
It’s called knowing your enemy. I have to know what I look like, and I have to know what other people look like, so I know if they’re repeating themselves to me, right?
Ok, so let’s do it one at a time, but let’s think about it, how do I know what a binary tree with my root looks like?
In fact, when you see this problem, you can judge that this problem is to use the “post-order traversal” framework to solve:
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
/* Location of solution code */
}
Copy the codeWhy is that? It’s very simple. If I want to know what my subtree looks like, do I have to know what my left and right subtrees look like, and then I add myself to the whole subtree?
If you can’t get around it, let me do a very simple example: calculate how many nodes there are in a binary tree. This code should write:
int count(TreeNode root) {
if (root == null) {
return 0;
}
// Calculate the number of nodes in the left and right subtrees
int left = count(root.left);
int right = count(root.right);
/* After traversing the code position */
// Add yourself to the total number of nodes in the binary tree
int res = left + right + 1;
return res;
}
Copy the codeThis is the standard post-order traversal framework, which is the same as what we did here.
Now that we know we’re going to go backwards, how do we describe what a binary tree looks like? The structure of a binary tree can be described by the result of pre-order/middle-order/post-order traversal.
So, we can serialize the binary tree by concatenating strings. Here’s the code:
String traverse(TreeNode root) {
// Empty nodes can be represented by a special character
if (root == null) {
return "#";
}
// Serialize the left and right subtrees into strings
String left = traverse(root.left);
String right = traverse(root.right);
/* After traversing the code position */
// Add the left and right subtrees to themselves to serialize the binary tree with itself as root
String subTree = left + "," + right + "," + root.val;
return subTree;
}
Copy the codeWe use the nonnumeric special character # to represent the null pointer, and we separate the value of each binary tree node with a character, which is the way we serialize binary trees, so to speak.
Note that subTree concatenates strings in order of left subTree, right subTree, and root node. You can concatenate strings either in front order or in middle order, because this is just describing what a binary tree looks like, it doesn’t matter what order.
This solves our first problem. For each node, the subTree variable in the recursive function can describe the binary tree with that node as the root.
Now let’s solve the second question. If I know what I look like, how do I know what other people look like? So I know if there are other subtrees that repeat to me.
We use an external data structure to let each node store the serialized result of its own subtree. This way, for each node, we can know if there are other nodes’ subtrees that duplicate our own.
The initial idea is to use HashSet to record subtrees as follows:
// Record all subtrees
HashSet<String> memo = new HashSet<>();
// Record the repeated child root node
LinkedList<TreeNode> res = new LinkedList<>();
String traverse(TreeNode root) {
if (root == null) {
return "#";
}
String left = traverse(root.left);
String right = traverse(root.right);
String subTree = left + "," + right+ "," + root.val;
if (memo.contains(subTree)) {
// Someone repeated with me, adding myself to the list of results
res.add(root);
} else {
// Add yourself to the set
memo.add(subTree);
}
return subTree;
}
Copy the codeBut, there’s a problem, because if you have multiple duplicate subtrees, there’s bound to be duplication in the result set RES, and they want to avoid duplication.
To solve this problem, we can update a HashSet to a HashMap, which records the occurrence of each subtree as an additional count:
// Record all subtrees and the number of occurrences
HashMap<String, Integer> memo = new HashMap<>();
// Record the repeated child root node
LinkedList<TreeNode> res = new LinkedList<>();
/* Main function */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return res;
}
/* Auxiliary function */
String traverse(TreeNode root) {
if (root == null) {
return "#";
}
String left = traverse(root.left);
String right = traverse(root.right);
String subTree = left + "," + right+ "," + root.val;
int freq = memo.getOrDefault(subTree, 0);
// Multiple repetitions are added to the result set only once
if (freq == 1) {
res.add(root);
}
// Add one to the number of occurrences of the subtree
memo.put(subTree, freq + 1);
return subTree;
}
Copy the codeSo, this problem is completely solved, and the problem itself is not difficult, but the idea of breaking it down is still quite enlightening, right?