题解 | #牛群的树形结构重建II#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param inOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* buildTreeII(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        // 已知中序遍历和先序遍历，重建二叉树; 
        if(inOrder.empty() || preOrder.empty())
            return nullptr;

        // 从先序遍历的数组中找到根节点 
        TreeNode* root = new TreeNode(preOrder.front());
       
        // index 的初始值不能为 -1，因为当inOrder.size()==0时，index将为-1，这样后面的左子树（右子树）的中序或者先序数组会越界; 
        // 不对，是因为当index=-1时，index<inOrder.size()结果竟然是false，我也是醉了，牛客的编译器搞毛呢？
        // int index = -1; 
        int index = 0;
        for(; index<inOrder.size(); ++index)
        {
            if(inOrder[index]==preOrder.front())
                break;
        }

        preOrder.erase(preOrder.begin());
        // cout << preOrder.front() << endl;
        // 如果有节点，则中序遍历和先序遍历的数组都不可能为空，所在index必定在[0,inOrder.size()-1]之间; 
        // 左子树的中序遍历 
        vector<int> left_inOrder(inOrder.begin(), inOrder.begin()+index);
        // 右子树的中序遍历 
        vector<int> right_inOrder(inOrder.begin()+index+1, inOrder.end());
        // 根据根节点在中序遍历中的位置，得到左右子树的“长度”，将后序遍历的数组分为左子树和右子树的后续遍历结果； 
        int len = index-0;
        // 左子树的先序遍历 
        vector<int> left_preOrder(preOrder.begin(), preOrder.begin()+len);
        // 右子树的先序遍历 
        vector<int> right_pretOrder(preOrder.begin()+len, preOrder.end());
        root->left = buildTreeII(left_preOrder,left_inOrder);
        root->right = buildTreeII(right_pretOrder,right_inOrder);

        return root;
    }
};