[数据结构与算法]【LeetCode-106 | 从中序与后序遍历序列构造二叉树】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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 nullptr;

        // 后序遍历数组的最后一个元素作为中序遍历数组的分割点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

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

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

        // 用找到的分割点将中序遍历数组一分为二[0, cutPoint) [cutPoint + 1, end)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + cutPoint);
        vector<int> rightInorder(inorder.begin() + cutPoint + 1, inorder.end());

        // 去除后序遍历数组的最后一个元素，因为它已经在中序遍历数组中作为分割点使用了
        postorder.resize(postorder.size() - 1);


        // 按照中序数组的大小作为后序遍历数组的切割点,将后序遍历数组一分为二[0, leftInorder.size()) [leftInorder.size(), end)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        // 递归处理左右区间
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }

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