题解 | #重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
class Solution {
public:
    TreeNode* reBuild(vector<int>& preorder,vector<int>& inorder) {
        if (preorder.size() == 0) return nullptr;
        
        // 找到先序遍历中的第一个元素就是根节点
        int rootValue = preorder[0];
        TreeNode* pRoot = new TreeNode(rootValue);
        
        // 找到中序遍历中的切割点
        int partition;
        for (partition = 0; partition < inorder.size(); ++partition) {
            if (inorder[partition] == rootValue) break;
        }

        // 切割中序数组，得到中序左子树和中序的右子树
        vector<int> leftInorder(inorder.begin(), inorder.begin() + partition);
        vector<int> rightInorder(inorder.begin() + partition + 1, inorder.end());

        // 切割先序数组，得到先序左子树和先序右子树
        // [ 1, leftInorder.size )
        vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
        // [leftInorder.size, end)
        vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end());

        // pRoot->left = reConstructBinaryTree(先序左子树, 中序左子树)
        // pRoot->right = reConstructBinaryTree(先序右子树, 中序右子树)

        pRoot->left = reConstructBinaryTree(leftPreorder, leftInorder);
        pRoot->right = reConstructBinaryTree(rightPreorder, rightInorder);
        return pRoot;
    }

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

};