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

#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, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd)
    {
        if(preorderBegin == preorderEnd) return nullptr;
        
        int rootValue = preorder[preorderBegin];

        TreeNode* root = new TreeNode(rootValue);

        if(preorderEnd - preorderBegin == 1) return root;

        int cutPoint;
        for(cutPoint = inorderBegin; cutPoint < inorderEnd; cutPoint++) {
            if(inorder[cutPoint] == rootValue) break;
        }

        // 切分中序遍历数组为左右两个区间:[inorderBegin, cutPoint)、[cutPoint + 1, inorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = cutPoint;

        int rightInorderBegin = cutPoint + 1;
        int rightInorderEnd = inorderEnd;

        // 切分前序遍历数组为左右两个区间：[preorderBegin + 1, preorderBegin + 1 + cutPoint - inorderBegin)、[preorderBegin + 1 + cutPoint - inorderBegin, preorderEnd)
        int leftPreorderBegin = preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + cutPoint - inorderBegin;

        int rightPreorderBegin = preorderBegin + 1 + cutPoint - inorderBegin;
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightPreorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
        return root;
    }

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