JZ7 rebuild binary tree

The given number of nodes is n The results of preorder traversal and inorder traversal of binary tree , Please rebuild the binary tree and return its head node .

For example, input preamble traversal sequence {1,2,4,7,3,5,6,8} And middle order ergodic sequence {4,7,2,1,5,3,8,6}, The reconstruction is as shown in the figure below .

 

The order of preorder traversal is ：root -> left -> right

The order of middle order traversal is : left -> root -> right

  The first element of preorder traversal , It must be the root node . In the center traversal ,root The front must be the left subtree ,root The next one must be the right subtree .

1. In the preamble traversal , Find the root node , namely pre[0], Initialization preamble 、 Traverse the range of data in the array in middle order preStart, preEnd, inStart, inEnd

2. In the middle order traversal , Find the location of the root node ,rootIndexInVin

3. Then according to the principle just , We can separate pre and vin According to the length of the data 、 The position of the left subtree determines the new preStart, preEnd, inStart, inEnd

  according to root The location of ,inStart, inEnd We can be sure ,inStart~rootIndexInVin - 1 It belongs to the left subtree , Can determine the left subtree inStart, inEnd

  alike , It can also be based on inStart, inEnd We can be sure ,rootIndexInVin + 1 ~ inEnd Belongs to the right subtree , Can determine the right subtree inStart, inEnd

  thus , We calculated , The length of the left subtree , The length of the right subtree ：

 

 4. According to the length of the left subtree and the right subtree , as well as preStart, preEnd Calculate the range of the left and right subtrees in the preorder traversal .

  We know , The first element in the preorder traversal is the root node , thus , from preStart + 1 Start , continued len(L) Each element is a left subtree , therefore , We can confirm the scope

preStart' = preStart + 1

preEnd' = preStart' + len(L) - 1 = (preStart + 1) + leftNodeLength - 1

  On the basis of the left subtree range , Further delay len(R) The first element is the right subtree range

preStart" = preEnd' + 1 = (preStart + 1 + leftNodeLength - 1) + 1

preEnd" = preStart" + len(R) - 1 =  (preStart + 1 + leftNodeLength - 1 + 1) + rightNodeLength - 1

Okay, so , Recursively complete the reconstruction of binary tree , Until all elements are traversed .

import java.util.*;
/**
 * 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 [] vin) {
        return construct(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
    }
    
    private TreeNode construct(int[] pre, int preStart, int preEnd, int[] vin, int inStart, int inEnd){
        if (pre == null || pre.length == 0 || vin == null || vin.length == 0){
            return null;
        }
        
        if (preStart > preEnd || inStart > inEnd){
            return null;
        }
        
        //  The first element of the preorder traversal is the current root node 
        int rootVal = pre[preStart];
        
        //  Find in the array traversed in middle order , Location of the root node 
        int rootIndexInVin = inStart;
        while (rootIndexInVin <= inEnd && vin[rootIndexInVin] != rootVal){
            rootIndexInVin++;
        }
        
        //  The left subtree nodes of the root node have a total of ：inStart~rootIndexInVin-1
        int leftNodeLength = rootIndexInVin - inStart;
        int rightNodeLength = inEnd - rootIndexInVin;
        
        TreeNode rootNode = new TreeNode(rootVal);
        rootNode.left = construct(pre, preStart + 1, (preStart + 1) + leftNodeLength - 1, vin, inStart, rootIndexInVin - 1);
        rootNode.right = construct(pre, (preStart + 1 + leftNodeLength - 1) + 1, (preStart + 1 + leftNodeLength - 1) + 1 + rightNodeLength - 1, vin, rootIndexInVin + 1, inEnd);
        
        return rootNode;
   }
}