[leetcode] construct a binary tree by traversing the sequence from front to middle (continuous optimization)

#LeetCode A daily topic 【 Special topic of binary tree 】

• Construction of binary trees from traversal sequences of preorder and middle order
  https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
• analysis
  Before the order ： root —— Left —— Right
  Middle preface ： Left —— root —— Right
  The first element of the preamble must be the root node , In the middle order , The element on the left of the root node is all the elements of the left subtree , The elements on the right of the root node are all the elements of the right subtree , Find the left subtree in the preordered sequence 、 The preorder sequence of the right subtree , In the recursive processing of the left and right subtrees
• Realization

	public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        if (preorder.length == 0) {
    
            return null;
        }
        int rootValue = preorder[0], len = preorder.length;
        if (len == 1) {
    
            return new TreeNode(rootValue);
        }
        //  Find Zuozi tree 、 Middle order of right subtree 
        int location = 0;
        for (int i = 0; i < len; i++) {
    
            if (inorder[i] == rootValue) {
    
                location = i;
                break;
            }
        }
        int[] leftInorder = new int[location];
        int[] rightInorder = new int[len - location - 1];
        System.arraycopy(inorder, 0, leftInorder, 0, location);
        System.arraycopy(inorder, location + 1, rightInorder, 0, rightInorder.length);

        //  Find the first order of the left subtree 、 Preorder of right subtree 
        int[] leftPreorder = new int[location];
        int[] rightPreorder = new int[rightInorder.length];
        System.arraycopy(preorder, 1, leftPreorder, 0, leftPreorder.length);
        System.arraycopy(preorder, 1 + leftPreorder.length, rightPreorder, 0, rightPreorder.length);

        TreeNode left = buildTree(leftPreorder, leftInorder);
        TreeNode right = buildTree(rightPreorder, rightInorder);
        return new TreeNode(rootValue, left, right);
    }

A large number of arrays are used copy
LeetCode Time consuming ：6ms

• Optimize
  Involving from the original array copy A new array for recursive processing , You can use the subscript of an array instead of , Start subscript 、 The end subscript indicates the range of an array .

public TreeNode buildTreeOptimize(int[] preorder, int[] inorder) {
    
        if (preorder == null || preorder.length == 0) {
    
            return null;
        }
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int preorderStart, int preorderEnd,
                               int inorderStart, int inorderEnd) {
    
        //  Recursion end condition 
        if (preorderStart > preorderEnd) {
    
            return null;
        }
        //  The first element of the preorder is the root node 
        int rootValue = preorder[preorderStart];
        //  The position of the root node in the middle order 
        int rootLocation = getIndexFromArray(rootValue, inorder, inorderStart, inorderEnd);
        //  Number of left subtree nodes 、 Length of the preorder array 
        int leftLength = rootLocation - inorderStart;
        //  Find the left and right subtrees and start with the middle order 、 Ending subscript 
        TreeNode left = buildTree(preorder, inorder, preorderStart + 1, preorderStart + leftLength,
                inorderStart, rootLocation - 1);
        TreeNode right = buildTree(preorder, inorder, preorderStart + leftLength + 1, preorderEnd,
                rootLocation + 1, inorderEnd);
        return new TreeNode(rootValue, left, right);
    }

    private int getIndexFromArray(int rootValue, int[] inorder, int inorderStart, int inorderEnd) {
    
        for (int i = inorderStart; i <= inorderEnd; i++) {
    
            if (inorder[i] == rootValue) {
    
                return i;
            }
        }
        return -1;
    }

LeetCode Time consuming ：3ms

• Optimizing
  Read the explanation of the question , The result of the middle order traversal is first represented by a map Store it , It is convenient to quickly retrieve the subscript according to the value each time , Space for time

Map<Integer, Integer> map = new HashMap<>();

    //  The idea is right , Find the first order of the left subtree 、 Middle preface ; Preorder of right subtree 、 Middle preface , Processing recursively 
    //  The original method is to copy a new array from the original array for each recursive processing , There are a lot of copies that take time 
    //  Based on this situation , You can use subscript movement , Instead of copying from the original array , Optimize 
    //  You need to know the subscript at the beginning of this round of recursive preorder 、 Ending subscript ; Subscript at the beginning of middle order 、 Ending subscript ;
    public TreeNode buildTreeOptimize(int[] preorder, int[] inorder) {
    
        if (preorder == null || preorder.length == 0) {
    
            return null;
        }
        //  Each time, you need to find the location of the root node from the middle order sequence , You need to loop through an article , Consider using space for time , Use map Store the value corresponding to the subscript in advance 
        for (int i = 0; i < inorder.length; i++) {
    
            map.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int preorderStart, int preorderEnd,
                               int inorderStart, int inorderEnd) {
    
        //  Recursion end condition 
        if (preorderStart > preorderEnd) {
    
            return null;
        }
        //  The first element of the preorder is the root node 
        int rootValue = preorder[preorderStart];
        //  The position of the root node in the middle order 
// int rootLocation = getIndexFromArray(rootValue, inorder, inorderStart, inorderEnd);
        Integer rootLocation = map.get(rootValue);
        //  Number of left subtree nodes 、 Length of the preorder array 
        int leftLength = rootLocation - inorderStart;
        //  Find the left and right subtrees and start with the middle order 、 Ending subscript 
        TreeNode left = buildTree(preorder, inorder, preorderStart + 1, preorderStart + leftLength,
                inorderStart, rootLocation - 1);
        TreeNode right = buildTree(preorder, inorder, preorderStart + leftLength + 1, preorderEnd,
                rootLocation + 1, inorderEnd);
        return new TreeNode(rootValue, left, right);
    }

LeetCode Time consuming ：1ms

• summary

1. Be familiar with the characteristics of pre order, middle order and post order , Find out the rules of constructing trees
2. Familiar with the application of tree recursion
3. Involving from the original array copy A new array for recursive processing , You can use the subscript of an array instead of , Start subscript 、 The end subscript indicates the range of an array