Sword finger offer 07 Rebuild binary tree

The finger of the sword Offer 07. Reconstruction of binary tree

recursive

class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        if(preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        //  Question 1 ： Find the location of the root node , adopt  HashMap  solve .
        int idx = 0;
        for(; idx < inorder.length; idx++){
    
            if(inorder[idx] == preorder[0]) break;
        }
        //  Question two ：java  Array cannot get subarray , Solve by copying or indexing .
        if(idx >= 0){
    
            root.left = this.buildTree(Arrays.copyOfRange(preorder, 1, idx + 1), Arrays.copyOfRange(inorder, 0, idx));
        }
        if(idx <= preorder.length - 1){
    
            root.right = this.buildTree(Arrays.copyOfRange(preorder, idx + 1, preorder.length), Arrays.copyOfRange(inorder, idx + 1, inorder.length));         
        }
        return root;
    }
}

	Root node preamble index	Middle order left boundary	Middle order right boundary
The left subtree	rootidx + 1	left	i - 1
Right subtree	rootidx + i - left + 1	i + 1	right

TIPS： i - left + rootidx + 1 It means Root node index + Left subtree length + 1

class Solution {
    
    HashMap<Integer, Integer> d = new HashMap<>(); //  Class variables 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        //  In the middle order, the root node divides the left and right subtrees  [left, idx), (idx, right)
        //  It is convenient to obtain the location of the root node 
        for(int i = 0; i < inorder.length; i++)
            d.put(inorder[i], i); 
        // rootidx = 0, left = 0, right = inorder.length - 1
        return recur(preorder, 0, 0, inorder.length - 1);
    }
	//  The root node index is at  preorder  Middle computation , The scope is  inorder  Middle computation .
    TreeNode recur(int[] preorder, int ridx, int left, int right) {
    
        if(left > right) return null;  //  Recursive termination 
        TreeNode node = new TreeNode(preorder[ridx]); //  Establish root node 
        int i = d.get(preorder[ridx]); //  The root node divides the left and right subtrees 
        node.left = recur(preorder, ridx + 1, left, i - 1); //  Turn on left subtree recursion 
        node.right = recur(preorder, ridx + i - left + 1, i + 1, right); //  Turn on right subtree recursion 
        return node;  
    }
}

iteration

class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        int n = preorder.length, idx = 0; // inorder  Indexes 
        if(preorder == null || n == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> q = new ArrayDeque<>();        
        q.push(root);
        
        for(int i = 1; i < n; i++){
     //  Traverse  preorder
            int val = preorder[i]; //  Antecedent value 
            TreeNode top = q.peek();
            if(top.val != inorder[idx]){
     //  Construct the left node 
                top.left = new TreeNode(val);
                q.push(top.left);
            } else {
    
                while(!q.isEmpty() && q.peek().val == inorder[idx]){
    
                    top = q.pop();
                    idx++; //  Traverse  inorder
                }
                top.right = new TreeNode(val);  //  Construct the right node 
                q.push(top.right);
            }
        }
        return root;
    }
}