Binary tree related creation or traversal

One 、 Through the first root traversal and the middle root traversal of the array , Build and restore binary tree

thought ： First root traversal array , The first element will be the root of the binary tree , Then find the position of the root in the root traversal , Then the child on the left of the middle root traversal is the left child , On the right is the right child . Using the idea of recursion .

public Node create(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
    Node root = new Node(pre[preStart], null, null);
    //  Recursion end condition 
    if(preStart == preEnd && inStart==inEnd){
        return root;
    }

    //  Find the position of the root in the root traversal , Identify the left child and the right child 
    int ft = 0;
    for(ft = inStart; ft < inEnd; ft++){
        if(in[ft] == pre[preStart]){
            break;
        }
    }

    //  Determine the number of left children 
    int left = ft - inStart;
    int rigth = inEnd - ft;
    //  There are left children , Then recursively establish the left child 
    if(left > 0 ){
        root.left = create(pre, in, preStart+1, preStart+left, inStart, ft -1);
    }
    
    if(right > 0){
        root.right = create(pre, in, preStart+left+1, preEnd, ft+1, inEnd);
    }
}

If it is followed by traversal and middle root traversal , The method is similar to , Mainly how to determine the relationship between the left child and the right child .

public Node create(int[] post, int[] in, int postStart, int postEnd, int inStart, int inEnd){
    //  Heel traversal , The last node is with 
    Node root = new Node(post[postEnd], null, null);
    if(postStart == postEnd && inStart == inEnd){
        return root;
    }

    //  Find the midpoint 
    int ft = 0;
    for(ft = inStart; ft < inEnd; ft++){
        if(in[ft] == post[postEnd]){
            break;
        }
    }

    int left = ft - inStart;
    int right = inEnd - ft;
    if(left > 0){
        root.left = create(post, in, postStart, postStart+left-1, inStart, ft -1);
    }

    if(right > 0){
        root.right = create(post, in, postStart+left, postEnd-1, ft+1, inEnd);
    }
}