Sword *offer04 rebuild binary tree

Title Description

Enter the results of preorder traversal and inorder traversal of a binary tree , Please rebuild the binary tree . It is assumed that the results of the input preorder traversal and the middle order traversal do not contain repeated numbers . 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}, Then rebuild the binary tree and return .

Answer key

Preorder traversal is to output first root The node is on the left node and then on the right node , Middle order traversal is first left then root Last right node

Traverse... According to the precedence , We can know the of this tree root node , namely root = pre[0], Then go to the middle order traversal to find root node , Middle order traversal root The left of the node is the left subtree , The one on the right is the right subtree .

1. Preface 1 2 4 7 3 5 6 8 ->root node 1
   Middle preface 4,7,2,1,5,3,8,6
   The left subtree Right subtree
   So we can get
   1 2 4 7 3 5 6 8->2 4 7 For the left subtree ,5 6 8 For the right subtree
2. recursive Regard the left and right subtrees as one tree ,root.left = reConstructBinaryTree(pr,ino);
   root.right = reConstructBinaryTree(pr,ino);
   Of course , If there is no number in the first sequence , That's it root The left side of the node / The right node is empty .
3. return root node .

/** * 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) {
    
        TreeNode root = new TreeNode(pre[0]);
        int length = pre.length;
        if(length==1){
    
            root.left = null;
            root.right = null;
            return root;
        }
        int location=0;
        for(int i = 0;i<in.length;i++){
    
            if(root.val == in[i]){
    
                location = i;
            }
        }
        
        if(location>0){
    
            int[] pr = new int[location];
            int[] ino = new int[location];
            for(int j =0;j<location;j++){
    
                pr[j]=pre[j+1];
                ino[j]=in[j];
            }
            root.left=reConstructBinaryTree(pr,ino);
        }else{
    root.left =null;}
        if(length-location-1>0){
    
		int[] pr=new int[length-location-1];
		int[] ino=new int[length-location-1];
		for(int j=location+1;j<length;j++){
    
			ino[j-location-1]=in[j];
			pr[j-location-1]=pre[j];
		}
		root.right=reConstructBinaryTree(pr,ino);
	}else{
    
		root.right=null;
	}
	
	
    return root;
    }
    
    
}