Leetcode 105. construct binary tree from preorder and inorder traversal sequence & 106. construct binary tree from inorder and postorder traversal sequence

Construction of binary trees from traversal sequences of preorder and middle order

Code implementation ：

import java.util.HashMap;
import java.util.Map;

/** * @Author Mr.Lu * @Date 2022/7/27 11:36 * @ClassName InorderAndPostOrderBuildTreeTest * @Version 1.0 */
public class InorderAndPreOrderBuildTreeTest {
    
    Map<Integer, Integer> map; //  It is convenient to find the position according to the value 
    public TreeNode buildTree(int[] preorder, int[] inorder){
    
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
      //  use map Save the corresponding position of the values of the middle order sequence 
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);  //  Before closed after opening 
    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
    
        //  The ranges in the parameters are all front closed and back open 
        if(preBegin >= preEnd || inBegin >= inEnd){
      //  Not satisfied with left close right open , There is no element , Returns an empty tree 
            return null;
        }

        int rootIndex = map.get(preorder[preBegin]); //  Find the position of the first element in the preorder traversal 
        TreeNode root = new TreeNode(inorder[rootIndex]);  //  Tectonic node 
        int lenOfLeft = rootIndex - inBegin; //  Save the number of left subtrees in the middle order , Used to determine the number of preordered sequences 

        root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin + 1, preBegin + lenOfLeft + 1);  //  The left array of sequence traversal and preorder traversal in recursive processing 
        root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft + 1, preEnd);  //  The right array of sequence traversal and preorder traversal in recursive processing 

        return root;
    }
}

Construct binary tree from middle order and post order traversal sequence

Code implementation ：

import java.util.HashMap;
import java.util.Map;

/** * @Author Mr.Lu * @Date 2022/7/27 11:36 * @ClassName InorderAndPostOrderBuildTreeTest * @Version 1.0 */
public class InorderAndPostOrderBuildTreeTest {
    
    Map<Integer, Integer> map;  //  It is convenient to find the position according to the value 
    public TreeNode buildTree(int[] inorder, int[] postorder){
    
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
    
            map.put(inorder[i], i);
        }
        
        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
    
        //  The ranges in the parameters are all front closed and back open 
        if(inBegin >= inEnd || postBegin >= postEnd){
      //  Not satisfied with left close right open , There is no element , Go straight back to 
            return null;
        }

        int rootIndex = map.get(postorder[postEnd - 1]); //  Find the position of the last element of the subsequent traversal in the middle order traversal 
        TreeNode root = new TreeNode(inorder[rootIndex]); //  Tectonic node 

        int lenOfLeft = rootIndex - inBegin; //  Save the number of left subtrees in the middle order , Used to determine the number of subsequent series 
        root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder,rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

Reference resources ： Random code recording https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#java