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

subject

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 last number of postorder traversal is the root node of the binary tree
• Find the corresponding position in the middle order traversal array according to the value of the root node , Then divide the middle order array into the left middle order traversal array , Right middle order traversal array
• Split the post order traversal array according to the length of the left and right middle order traversal array .

Code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    TreeNode* traversal(vector<int>& inorder,vector<int>& postorder)
    {
    
        if(postorder.size() == 0) return NULL;

        //  The last element of the post order traversal array is the root node of the binary tree 
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        //  Leaf node 
        if(postorder.size() == 1)
        {
    
            return root;
        }

        //  Find the cutting point of the middle order traversal 
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++)
        {
    
            if(inorder[delimiterIndex] == rootValue)
            {
    
                break;
            }
        }

        //  Divide the medium order array 
        //  Left closed right open interval ：[0,delimiterIndex)
        vector<int> leftInorder(inorder.begin(),inorder.begin() + delimiterIndex);

        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1,inorder.end());

        //  Discard end element 
        postorder.resize(postorder.size() - 1);

        //  Cut sequential array   Divide according to the length of the middle order left array and the middle order right array 
        vector<int> leftPosterorder(postorder.begin(),postorder.begin() + leftInorder.size());
        vector<int> rightPosterorder(postorder.begin() + leftInorder.size(),postorder.end());

        root->left = traversal(leftInorder,leftPosterorder);
        root->right = traversal(rightInorder,rightPosterorder);

        return root;

    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    
        if(inorder.size() == 0 || postorder.size() == 0)
        {
    
            return NULL;
        }

        return traversal(inorder,postorder);
    }
};