二叉树 – 从中序和后序序列构造二叉树

从中序与后序遍历序列构造二叉树该题主要考察对中序和后序遍历的理解与递归的运用。

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

中序：左中右

后序：左右中

经典步骤：

• 1 先通过后序的中（根节点），确定中序的切割点
• 2 对中序进行切割，得到左子树数组和右子树数组
• 3 对后序进行切割，根据中序数组的长度切分得到后序的左右子数组
• 4 递归处理中序和后序对二叉树进行构建

代码如下：

/**
 * 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& inorder, vector& postorder){
        // 1 判空
        if(postorder.size() == 0) return nullptr;

        // 2 去后序数组中根节点
        int rootValue = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(rootValue);

        // 3 判断是否只有一个节点
        if (postorder.size() == 1) return root;

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

        // 5 对中序数组进行切割
        vector leftInorder(inorder.begin(), inorder.begin()+delimiterIndex);
        vector rightInorder(inorder.begin()+delimiterIndex+1, inorder.end());
        // postorder.resize(postorder.size()-1);

        // 6 对后序数组进行切割
        vector leftPostorder(postorder.begin(), postorder.begin()+leftInorder.size());
        vector rightPostorder(postorder.begin()+leftInorder.size(), postorder.end()-1);
        
        // 7 递归
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
        return root;
    }

    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if (inorder.size()==0 || postorder.size()==0) return nullptr;
        return traversal(inorder, postorder);
    }
};