Leetcode problem solving - 889 Construct binary tree according to preorder and postorder traversal

private int[] pre
private int[] post;

public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
    
    pre = preorder;
    post = postorder;
    return buildTree(0,0,pre.length);
}

private TreeNode buildTree(int i,int j,int n){
    
    if (n==0) return null;
    TreeNode root = new TreeNode(pre[i++]);
    if (n==1) return root;
    int L = 1;
    for (;L<n;L++) if (post[j+L-1]==pre[i])  break; 
    root.left = buildTree(i,j,L);
    root.right = buildTree(i+L,j+L,n-1-L);

    return root;
}

Ideas ：
The first thing to know is
The former sequence traversal
[ The root node ,( The left subtree ),( Right subtree )]
After the sequence traversal
[( The left subtree ),( Right subtree ), The root node ]
that , We can know that the root node is the first element in the preorder traversal , So how to divide the left and right subtrees ？ If we know the length of the left subtree, can we divide the left and right subtrees ？ How to get the length ？
Where will the root node of the left subtree in the pre order traversal appear in the left subtree in the post order traversal ？
The answer is ： the last one
That is to say ：pre[1]==post[L-1]
set up i Traverse the first element index of the left subtree for the previous order ,j Traverse the index of the first element of the left subtree for the post order , Yes pre[i]=post[j+L-1]
Thus, the left and right subtrees can be divided for the next recursion

• take preorder and postorder Member variables stored in the class , It reduces the cumbersome process of transferring parameters
• At the beginning , The index of the first element of the pre order traversal of the left subtree is 1, But the answer is 0, This is because you need to create the root node first , After creating i It's going to increase 1, The index of the first element of the left subtree traversed by the latter order is 0, That is to say, it's passed on 0, And passed the length of the subtree node
• If the subtree length is 0, Go straight back to null, by 1, Then create the root node and return , Longer than 1, Continue to divide the left and right subtrees
• Loop to get the length of the left subtree , Continue to recursively create left and right subtrees
• return root