Rebuilding binary tree

• Examination Points: Trees
• Time limit: 1 second
• Space limitation: 32768K
• Enter the results of the pre-order and middle-order traversals of a binary tree, and rebuild the binary tree. It is assumed that the results of the input preamble traversal and the intermediate order traversal do not contain duplicate numbers. For example, the binary tree is reconstructed and returned if the pre-order traversal sequence {1,2,4,7,3,5,6,8} and the middle-order traversal sequence {4,7,2,1,5,3,8,6} are input.

Ideas:

[See other ideas 1 to understand the idea of the algorithm, other ideas 2 is a relatively easy to understand code version, the following is the most concise, but a little difficult to understand. ]

The first place to traverse in sequence must be the root node.
The root node of the intermediate traversal is located in the middle p, the middle array of the left subtree of node must be on the left side of p, and the middle array of the right subtree of node must be on the right side of P.
On the other hand, the second position of the precedence traversal to p is also the precedence subarray of the left subtree of node, and the precedence subarray of the right subtree of node is left to the right of P.
Find out the four arrays and call them recursively.

Code:

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        // Judging Legitimacy
        if (pre == null || in == null || pre.length < 0 || in.length < 0) {
            return null;    
        }
        return reconstructTree(pre, 0, pre.length - 1, in, 0, pre.length - 1);
    }
    
    public TreeNode reconstructTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) {
            return null;
        }
        
        // The first element is the root element.
        int value = pre[startPre];
        TreeNode root = new TreeNode(value);
        
        // Find the location of the intermediate traversal root node
        int index = 0;
        for (index = 0; index < in.length; index++) {
            if (in[index] == value)
                break;
        }
        
        root.left = reconstructTree(pre, startPre + 1, startPre + index - startIn, in, startIn, index - 1);
        root.right = reconstructTree(pre, startPre + index - startIn + 1, endPre, in, index + 1, endIn);
        
        return root;
        
    }
}

My question:

1. Note that the array is 0, or that the length of the middle-order traversal and the first-order traversal array is inconsistent. (Illegal Data Processing)
2. I-startIn calculates the number of nodes in the left subtree of the current node; i-startIn+startPre determines the location of the left subtree of the current node in the pre; according to the characteristics of intermediate traversal+preceding traversal, pre[startPre+1] is the left subtree of the current node, and pre[i-startIn+startPre+1] is the right subtree of the current node; The criterion is that the left and right sub-nodes do not exist when crossing the boundary.
3. root.left = reconstructTree(pre, startPre + 1, i - startIn + startPre, in, startIn, i - 1);
   root.right = reconstructTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
   I-startIn is the left subtree length.
   That is, i is the root node in the middle.

pre:
[startPre + 1, i - startIn + startPre]
[i - startIn + startPre + 1, endPre]

in:
[startIn, i - 1]
[i + 1, endIn]

Other ideas:

Because it is the structure of trees, it is usually realized by recursion.
The idea of mathematical induction is that if the last step is that the left and right subtrees of root have been reconstructed, then I just need to consider installing the left and right subtrees of root.
According to the nature of preorder traversal, the first element must be root, so the following work is how to determine the range of left and right subtrees of root.
According to the nature of intermediate traversal, the root element is preceded by the left subtree of root, followed by the right subtree of root. Then we can determine the range of left and right subtrees by finding the location of root in the middle order traversal.
As mentioned above, you just need to place the determined left and right subtrees on the root. Recursion should pay attention to the exit, assuming that there is only one element at the end, then return.

import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //Processing when array length is 0
        if(pre.length == 0){
            return null;
        }
 
        int rootVal = pre[0];
 
        //Processing when the array length is only 1
        if(pre.length == 1){
            return new TreeNode(rootVal);
        }
 
        //We first find the location of root and determine the range of left and right subtree sequences in preface and middle order.
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = 0;
        for(int i=0;i<in.length;i++){
            if(rootVal == in[i]){
                rootIndex = i;
                break;
            }
        }
 
        //Recursion. Assuming that the left and right subtrees of root have been constructed, just install the left and right subtrees to the left and right subtrees of root.
        //Note here that Arrays.copyOfRange(int[],start,end) is an interval of [.
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));
 
        return root;
    }
}

In fact, that's how he divided it:
pre:
[1, rootIndex]
[rootIndex + 1, pre.length - 1]

in:
[0, rootIndex -1]
[rootIndex + 1, in.length - 1]

Separate the left and right subtrees, and then use Arrays.copyOfRange(int[],start,end).
This function is the interval of [. Scope of attention.
Unfortunately, the function Arrays.copyOfRange() is not used in Niuke.com. But I do see that understanding.

Other ideas 2:

This is relatively easy to understand, because this is a self-replicating array.
The length of the left array is rootIndex.
The length of the right array is x.length - rootIndex - 1. (minus 1 is to subtract the root node)
The array is then scanned for replication.
Then it's probably replicated like this. It's pre on the top, in the middle, and a new array on the bottom. The arrow points to the corresponding element of the replicate.
[External Link Picture Transfer Failure (img-zPi4A1G2-1565666087930)(en-resource://database/2079:1)]

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        // Judgment of Illegal Conditions
        if (pre.length == 0 || in.length == 0 || pre.length != in.length) {
            return null;
        }
        
        // Create the root node
        TreeNode root = new TreeNode(pre[0]);
        int rootIndex = 0;
        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                rootIndex = i;
                break;
            }
        }
        
        // Create four new arrays
        int[] preLeft = new int[rootIndex];
        int[] inLeft = new int[rootIndex];
        int[] preRight = new int[pre.length - rootIndex- 1];
        int[] inRight = new int[in.length - rootIndex - 1];
        // Duplicate arrays
        for(int j = 0; j < in.length; j++) {
            if (j < rootIndex) {
                preLeft[j] = pre[j + 1];
                inLeft[j] = in[j];
            } else if (j > rootIndex) {
                preRight[j - rootIndex - 1] = pre[j];
                inRight[j - rootIndex -1] = in[j];
            }
        }
        root.left = reConstructBinaryTree(preLeft, inLeft);
        root.right = reConstructBinaryTree(preRight, inRight);
        return root;
    }
}