Leetcode 106. 从中序与后序遍历序列构造二叉树

题目

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

• 后序遍历的最后一个数就是二叉树的根节点
• 根据根节点的值在中序遍历数组中找到对应的位置，然后分割中序数组为左中序遍历数组，右中序遍历数组
• 根据左右中序遍历数组的长度来拆分后序遍历数组。

代码

/** * 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;

        // 后序遍历数组的最后一个元素就是二叉树的根节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // 叶子节点
        if(postorder.size() == 1)
        {
    
            return root;
        }

        // 找到中序遍历的切割点
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++)
        {
    
            if(inorder[delimiterIndex] == rootValue)
            {
    
                break;
            }
        }

        // 划分中序数组
        // 左闭右开区间：[0,delimiterIndex)
        vector<int> leftInorder(inorder.begin(),inorder.begin() + delimiterIndex);

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

        // 舍弃末尾元素
        postorder.resize(postorder.size() - 1);

        // 切割后序数组 根据中序左数组和中序右数组的长度进行划分
        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);
    }
};