Sword finger offer07 Rebuild binary tree

The finger of the sword Offer07. Reconstruction of binary tree

Title Description

Enter the results of preorder traversal and inorder traversal of a binary tree , Build the binary tree and return its root node .
It is assumed that the results of the input preorder traversal and the middle order traversal do not contain repeated numbers .

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Limit ：

0 <= Number of nodes <= 5000

JAVA Code

Recursive method

Refer to the solution in tianqin book .

** design idea ：** The first element in the sequence is traversed first x That is, the root node value of the tree . Found in middle order traversal x, utilize x Divide the array traversed in middle order into two subsequences , The left sequence forms the left subtree of the tree , The right sequence forms the right subtree of the tree , Then treat the left and right subsequences in the same way , Until there is only one element left in the processed subsequence , The construction of binary tree is completed .

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        int n = preorder.length;
        TreeNode node = createTree(preorder,inorder,0,n-1,0,n-1);
        return node;
    }

	// Building a binary tree 
    public TreeNode createTree(int[] preorder, int[] inorder,int L1,int R1,int L2,int R2){
    
        TreeNode node;
        int i;
        if(L1>R1){
    
            return null;
        }
        node = new TreeNode();
        node.left=node.right=null;
        for(i = L2;i<=R2;++i){
    
            if(inorder[i]==preorder[L1]){
    
                break;
            }
        }
        node.val = inorder[i];
        node.left = createTree(preorder,inorder,L1+1,L1+i-L2,L2,i-1);
        node.right = createTree(preorder,inorder,L1+i-L2+1,R1,i+1,R2);
        return node;
    }
}

official – Iterative method

Iterative non recursive method .
The idea can be based on the non recursive implementation of binary tree traversal .
The non recursive method of binary tree is hard to understand , So I'll add it here when I have learning needs in the future .
For the time being, I feel that recursion is enough . I can't understand it, so I don't bother to waste time .