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

/** 
 * 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 inOrder int整型vector  
     * @param postOrder int整型vector  
     * @return TreeNode类 
     */ 
    TreeNode* buildTree(vector<int>& inOrder, vector<int>& postOrder) {
        // write code here 
        // 已知中序遍历后后续遍历，重建二叉树; 
        if(inOrder.empty() || postOrder.empty())
            return nullptr;
       
        // 从后续遍历的数组中找到根节点 
        TreeNode* root = new TreeNode(postOrder.back());
       
        // 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]==postOrder.back())
                break;
        }
        postOrder.pop_back();
        // 如果有节点，则中序遍历和后序遍历的数组都不可能为空，所在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_postOrder(postOrder.begin(), postOrder.begin()+len);
        // 右子树的后序遍历 
        vector<int> right_postOrder(postOrder.begin()+len, postOrder.end());
        root->left = buildTree(left_inOrder, left_postOrder);
        root->right = buildTree(right_inOrder, right_postOrder);
        return root;
    }
};