Recursive method constructs binary tree from middle order and post order traversal sequence

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

Medium difficulty

Given two arrays of integers inorder and postorder , among inorder Is the middle order traversal of a binary tree , postorder Is the post order traversal of the same tree , Please construct and return this Binary tree .

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 last one in the subsequent traversal is the current node , Its left subtree and right subtree are on its left

We can find the current node according to the subsequent 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 subsequent traversal , But you can get this value from the middle order traversal

Specific please see 37 And 38 That's ok

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

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

/** * 106.  Construct binary tree from middle order and post order traversal sequence  *  Given two arrays of integers  inorder  and  postorder , among  inorder  Is the middle order traversal of a binary tree , postorder  Is the post order traversal of the same tree , Please construct and return this   Binary tree  . * <p> * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ */
public class Solution {
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    
        return helpBuild(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode helpBuild(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
    
        //  There are no elements 
        if (inRight - inLeft < 1) {
    
            return null;
        }
        //  There's only one element 
        if (inRight - inLeft == 1) {
    
            return new TreeNode(inorder[inLeft]);
        }
        //  The last element in the subsequent array is the root node 
        int rootVal = postorder[postRight - 1];
        TreeNode root = new TreeNode(rootVal);
        //  Find the position of the root node in the ordered array 
        int rootIndex = 0;
        for (int i = inLeft; i < inRight; i++) {
    
            if (inorder[i] == rootVal) {
    
                rootIndex = i;
                break;
            }
        }
        
        root.left = helpBuild(inorder, inLeft, rootIndex, postorder, postLeft, postLeft + (rootIndex - inLeft));
        root.right = helpBuild(inorder, rootIndex + 1, inRight, postorder, postLeft + (rootIndex - inLeft), postRight - 1);
        return root;
    }
}