Recursive method to construct binary tree from preorder and inorder traversal sequence

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

Medium difficulty

Given two arrays of integers preorder and inorder , among preorder It's a binary tree The first sequence traversal , inorder It's from the same tree In the sequence traversal , Please construct a binary tree and return its root node .

Ideas

The knowledge points that need to be understood are ：

• In the middle order traversal, the left side of a node is all nodes of its left subtree , On the right are all the nodes of its right subtree
• The first node in the preorder traversal is the current node , Its left subtree and right subtree are on its right

We can find the current node according to the previous traversal , Then find the position of the current root node in the ordered array , Then the range of the new left subtree and right subtree is determined by the position of the root node and the range of its subtree , Then recurs continuously , Until the last traversal of the entire array .

We cannot determine the range of left subtree and right subtree in the preceding traversal , But you can get this value from the middle order traversal

Specific please see 32 And 33 That's ok

package cn.edu.xjtu.carlWay.tree.preAndInConstructBinaryTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 105.  Construction of binary trees from traversal sequences of preorder and middle order  *  Given two arrays of integers  preorder  and  inorder , among  preorder  Is the prior traversal of a binary tree , inorder  Is the middle order traversal of the same tree , Please construct a binary tree and return its root node . * <p> * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ */
public class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        return helpBuild(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode helpBuild(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
    
        if (inRight - inLeft == 0) {
    
            return null;
        }
        if (inRight - inLeft == 1) {
    
            return new TreeNode(inorder[inLeft]);
        }
        TreeNode root = new TreeNode(preorder[preLeft]);
        int rootIndex = 0;
        for (int i = inLeft; i < inRight; i++) {
    
            if (inorder[i] == root.val) {
    
                rootIndex = i;
                break;
            }
        }

        root.left = helpBuild(preorder, preLeft + 1, preLeft + 1 + (rootIndex - inLeft), inorder, inLeft, rootIndex);
        root.right = helpBuild(preorder, preLeft + 1 + (rootIndex - inLeft), preRight, inorder, rootIndex + 1, inRight);

        return root;
    }
}