Enter the results of preorder and middle order traversal of a binary tree, please rebuild the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.
For example, given
Preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Copy the codeReturn the following binary tree:
3
/ \
9 20
/ \
15 7
Copy the code
Limitations:
0 <= Number of nodes <= 5000
The answer:
1. Recursion
So before we do that, let’s look at a couple of ways we can traverse a tree.
Sequential traversal: root node → left subtree → right subtree.
Middle order traversal: left subtree → root node → right subtree.
Subsequent traversal: left subtree → right subtree → root node.
Actually very easy to remember, also he is defined according to the root node traversal sequence, such as the first traverse the root node is the first sequence traversal, traverse the root node is in sequence traversal, finally through the root node is the subsequent traversal, as for the left child which first traversal tree and right subtree, remember that the 3 kinds of traversal sequence will never be better than the left right node traversal first. If you don’t already know, look at 373 data structure 6 tree.
Let’s take a look at the above example data. The pre-order traversal is [3,9,20,15,7]. The pre-order traversal first visits the root node, so 3 is the root node. The middle order traversal is [9,3,15,20,7]. Since the root node is traversed only when the left subtrees are traversed, all the nodes before 3 in the middle order traversal are left subtree nodes of 3, and all the nodes after 3 are right subtree nodes of 3. So it’s going to look like this
And then we divide the left and right subtrees in the same way, and so on, until we can’t divide any more, so let’s look at the code
public TreeNode buildTree(int[] preorder, int[] inorder) {
// Place the preceding and middle traversal values in the list
List<Integer> preorderList = new ArrayList<>();
List<Integer> inorderList = new ArrayList<>();
for (int i = 0; i < preorder.length; i++) {
preorderList.add(preorder[i]);
inorderList.add(inorder[i]);
}
return helper(preorderList, inorderList);
}
private TreeNode helper(List<Integer> preorderList, List<Integer> inorderList) {
if (inorderList.size() == 0)
return null;
// The first value of the pre-traversal is the root node
int rootVal = preorderList.remove(0);
// create the following node
TreeNode root = new TreeNode(rootVal);
// Check the position of the root node in the middle traversal, and then split the middle traversal array in half
// All values of the left subtree of the root node, followed by all values of the right subtree of the root node
int mid = inorderList.indexOf(rootVal);
//[0, mid) is all the values of the left subtree, inorderList.subList(0, mid) is truncated inorderList
//, the range of interception is [0, mid), including 0 but not including mid.
root.left = helper(preorderList, inorderList.subList(0, mid));
//[mid+1, inorderList.size()))
// inorderList.sublist (mid + 1, inorderList.size())
[mid+1, inorderList.size())), mid+1 does not contain inorderList.size().
root.right = helper(preorderList, inorderList.subList(mid + 1, inorderList.size()));
return root;
}
Copy the codeThe above code converts the array to a list and then intercepts it in a list, which is obviously not very efficient. In fact, we can skip the list and not intercept the array.
2. Use Pointers
We only need to use three Pointers. One is preStart, which represents the beginning of the preceding traversal, and the other is inStart, which represents the beginning of the middle traversal. One is inEnd, which represents the position at the end of middle-order traversal. We mainly disassemble the array of middle-order traversal. Let’s draw a diagram for analysis of the tree below
His prior traversal is: [3,9,8,5,2,20,15,7]
His middle-order traversal is: [5,8,9,2,3,15,20,7]
As long as we find the position of the node of the preceding traversal in the middle traversal, we can split the middle traversal into two parts. If index is the index of a value of the preceding traversal in the middle traversal number group, divided by index as the root node, then in the middle traversal
[0, index-1] is all nodes in the left subtree of the root node,
[index+1, inorder.length-1] is all nodes in the right subtree of the root node.
Middle traversal is easy to partition, but what about pre-traversal, if it is a left subtree:
PreStart = index + 1;
If it’s a right subtree it’s a little bit more difficult,
PreStart = preStart + (index – instart + 1);
PreStart (index-instart+1) is the number of left subtrees of current node M plus the number of current nodes, so preStart+(index-instart+1) is the number of right subtrees of current node M. Let’s look at the complete code
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0.0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
// Create a node
TreeNode root = new TreeNode(preorder[preStart]);
int index = 0;
// Find the position of the current node root in the middle order traversal, and then divide the number in half
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
index = i;
break;
}
}
root.left = helper(preStart + 1, inStart, index - 1, preorder, inorder);
root.right = helper(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder);
return root;
}
Copy the code
3, use stack solution
If you use a stack, the first thing you need to understand is that if you go through two values next to each other like m and n, they have one of the following relationships.
1, n is the value of the left subtree node of M.
2, n is the value of the right subtree node of M or the right node of one of m’s ancestors.
-
If the left subtree of M is not empty, then n is the value of the left subtree of M.
-
For the second problem, if a node has no left subtree and only a right subtree, then n is the value of the right subtree of M, and if a node has neither left subtree nor right subtree, then n is the right node of some ancestor of M, and we just need to find that ancestor.
Once you understand this, the code is easy to write, so let’s look at the complete code
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0)
return null;
Stack<TreeNode> s = new Stack<>();
// The first of the preorders is actually the root node
TreeNode root = new TreeNode(preorder[0]);
TreeNode cur = root;
for (int i = 1, j = 0; i < preorder.length; i++) {
// The first case
if(cur.val ! = inorder[j]) { cur.left =new TreeNode(preorder[i]);
s.push(cur);
cur = cur.left;
} else {
// The second case
j++;
// Find the appropriate cur, and then determine his right node
while(! s.empty() && s.peek().val == inorder[j]) { cur = s.pop(); j++; }// Add the right node to cur
cur = cur.right = newTreeNode(preorder[i]); }}return root;
}
Copy the code
4. Another solution to recursion
We know that the first element of the pre-order traversal must be the root node, so the first node of the pre-order traversal before the middle position is the left child of the root node, and the next node is the right child of the root node. Let’s draw a simple diagram
So just to give you a random example, we see that the 3 before the preceding traversal must be the root, so in the middle traversal, everything before 3 is the value of the left child of 3, everything after 3 is the value of the right child of 3,
His real structure is this
Let’s look at the code
private int in = 0;
private int pre = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, Integer.MIN_VALUE);
}
private TreeNode build(int[] preorder, int[] inorder, int stop) {
if (pre >= preorder.length)
return null;
if (inorder[in] == stop) {
in++;
return null;
}
TreeNode node = new TreeNode(preorder[pre++]);
node.left = build(preorder, inorder, node.val);
node.right = build(preorder, inorder, stop);
return node;
}
Copy the code