题解 | #重建二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* travel(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.size() == 0) return nullptr;
        int rootval = preOrder[0];
        // 根据前序遍历找到中间节点
        TreeNode* root = new TreeNode(rootval);
        if (vinOrder.size() == 1) return root;
        // 找到切割点，然后切割数组
        int divideIndex = 0;
        for (divideIndex; divideIndex < vinOrder.size(); ++divideIndex){
            if (vinOrder[divideIndex] == rootval) break;
        }
        // 此时divideIndex代表的是切割点下标
        // 开始切割前序 中序数组
        std::vector<int> vinLeftOrder(vinOrder.begin(), vinOrder.begin() + divideIndex);
        std::vector<int> vinRightOrder(vinOrder.begin() + divideIndex + 1, vinOrder.end());
        // 切割前序数组，需要删除前序的第一个元素
        preOrder.erase(preOrder.begin());
        std::vector<int> preLeftOrder(preOrder.begin(), preOrder.begin() + vinLeftOrder.size());
        std::vector<int> preRightOrder(preOrder.begin() + vinLeftOrder.size(), preOrder.end());
        // 继续递归得到左子树头节点 右子树头节点
        root->left = travel(preLeftOrder, vinLeftOrder);
        root->right = travel(preRightOrder, vinRightOrder);
        return root;
    }

    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        if (preOrder.size() == 0 && vinOrder.size() == 0) return nullptr;;
        return travel(preOrder, vinOrder);
    }
};