Leetcode skimming: binary tree 17 (construct binary tree from middle order and post order traversal sequence)

106. Construct binary tree from middle order and post order traversal sequence

Force button topic link

According to the middle order traversal and post order traversal of a tree, a binary tree is constructed .

Be careful :
You can assume that there are no duplicate elements in the tree .

for example , give

In the sequence traversal inorder = [9,3,15,20,7]
After the sequence traversal postorder = [9,15,7,20,3]
Return to the following binary tree ：

The difficulty is good , Recursive method . The termination condition is The length of both arrays is 0 when , return null . After the sequence traversal Left Right root . Every time the post order traversal is constructed , The last of the subsequent array is always the root node , Then according to this root node , There are also subject regulations No repeating elements , Then find the current root node in the ordered array , Take it as the boundary to divide the middle order array into the middle order array of the left subtree and the middle order array of the right subtree . And in the middle order array Root node The location of , Just put it in the subsequent array , This position is forward yes Postorder traversal of left subtree , This position includes the position backwards until The next to last element Is the postorder traversal of the right subtree , The last one is the root node .
Then take the first of the left subtree 、 Post array and First of right subtree 、 The last array can be recursive .

package com.programmercarl.tree;

/** * @ClassName BuildTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 12:37 * @Version 1.0 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ * 106.  Construct binary tree from middle order and post order traversal sequence  **/
public class BuildTree {
    
    /** * @param inorder  In the sequence traversal  1 2 * @param postorder  After the sequence traversal  2 1 * @return */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    
        if (inorder.length == 0 && postorder.length == 0) {
    
            return null;
        }
        // The length of the last array is equal , Because the number of elements is the same 
        // The first element of post order traversal is the root node 
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        // Find the root node in the middle order traversal 
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
    
            if (root.val == inorder[i]) {
    
                rootIndex = i;
            }
        }
        // The medium order array is divided into left subtree and right subtree 
        int[] leftIn = new int[rootIndex];
        int[] rightIn = new int[inorder.length - rootIndex - 1];
        for (int i = 0; i < inorder.length; i++) {
    
            if (i < rootIndex) {
    
                leftIn[i] = inorder[i];
            } else if (i > rootIndex) {
    
                rightIn[i-rootIndex-1] = inorder[i];
            }
        }
        // After order traversal array   front rootIndex Bit is left subtree , after rootIndex Bit is a right subtree 
        int[] leftPost = new int[rootIndex];
        int[] rightPost = new int[inorder.length - rootIndex - 1];
        // The last node , It has been built as the root node .
        for (int i = 0; i < postorder.length - 1; i++) {
    
            if (i < rootIndex) {
    
                leftPost[i] = postorder[i];
            } else {
    
                rightPost[i - rootIndex] = postorder[i];
            }
        }
        // Construct left and right subtrees 
        root.left = buildTree(leftIn, leftPost);
        root.right = buildTree(rightIn, rightPost);
        return root;
    }

    public static void main(String[] args) {
    
        new BuildTree().buildTree(new int[]{
    1, 2}, new int[]{
    2, 1});
    }
}