Subject to introduce

Force buckle 105: leetcode-cn.com/problems/co…

Analysis of the

The function signature is as follows:

TreeNode buildTree(int[] preorder, int[] inorder);

So let’s go ahead and think about what the root node should do.

Just like we did in the last problem, we definitely have to figure out how to determine the root node, figure out the root node, and then recursively construct the left and right subtrees.

Let’s first review, what are the characteristics of the results of pre-order traversal and middle-order traversal?

void traverse(TreeNode root) {
    // preorder traversal
    preorder.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

void traverse(TreeNode root) {
    traverse(root.left);
    // middle order traversal
    inorder.add(root.val);
    traverse(root.right);
}
Copy the code

This traversal order difference results in the distribution of elements in the preorder and inorder arrays as follows:Finding the root node is easy. The first value preorder[0] is the value of the root node. The key is how to divide the preorder and Postorder arrays into two halves by using the value of the root node.

In other words, for? What should be filled in the section:

/* Main function */
TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

/* If preorder[preStart..preEnd] and postorder[postStart..postEnd], construct a binary tree and return the root node of the binary tree */
TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {
    The value of the root node is the first element in the sequence traversal array
    int rootVal = preorder[preStart];
    // rootVal Traverses the index in the group in the middle order
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    TreeNode root = new TreeNode(rootVal);
    // Construct left and right subtrees recursivelyroot.left = build(preorder, ? ,? , inorder, ? ,?) ; root.right = build(preorder, ? ,? , inorder, ? ,?) ;return root;
}
Copy the code

For rootVal and index variables in the code, this looks like the following:Now let’s look at the picture and fill in the blanks. What should be filled in the following question marks?

root.left = build(preorder, ? ,? , inorder, ? ,?) ; root.right = build(preorder, ? ,? , inorder, ? ,?) ;Copy the code

It is easy to determine the starting and ending indexes of the inorder array corresponding to the left and right subtrees:

root.left = build(preorder, ? ,? , inorder, inStart, index -1); root.right = build(preorder, ? ,? , inorder, index +1, inEnd);
Copy the code

What about the preorder array? How do I determine the starting and ending indexes for left and right arrays?

This can be deduced from the number of nodes in the left subtree. Assuming the number of nodes in the left subtree is leftSize, the index on the preorder array looks like this:Look at this graph to write the index corresponding to preorder:

int leftSize = index - inStart;

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1);

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd);
Copy the code

At this point, the whole algorithm idea is completed, we can fill up the base case to write the solution code:

TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {

    if (preStart > preEnd) {
        return null;
    }

    The value of the root node is the first element in the sequence traversal array
    int rootVal = preorder[preStart];
    // rootVal Traverses the index in the group in the middle order
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break; }}int leftSize = index - inStart;

    // Construct the current root node
    TreeNode root = new TreeNode(rootVal);
    // Construct left and right subtrees recursively
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, index - 1);

    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, index + 1, inEnd);
    return root;
}
Copy the code

Our main function simply calls the build function. It’s a bit daunting to see how many arguments the function has and how much code it can solve. In fact, all the arguments control where the array starts and ends.