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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
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 (postOrder.size() == 0)
        {
            return NULL;
        }
        //后续遍历的最后一个元素是根节点
        TreeNode* root = new TreeNode(postOrder[postOrder.size() - 1]);
        //从根节点中分割中序遍历数组,分割以后就是左子树和右子树
        int index = 0;
        for (int i = 0;i < inOrder.size();++i)
        {
            if (inOrder[i] == postOrder[postOrder.size() - 1])
            {
                index = i;
                break;
            }
        }
        vector<int> leftTree(inOrder.begin(),inOrder.begin() + index);
        vector<int> rightTree(inOrder.begin() + index + 1,inOrder.end());
        //此时后续遍历最后一个节点就没有用了，要及时删去
        //postOrder.erase(postOrder.end());
        postOrder.resize(postOrder.size() - 1);
        //根据分割出的左子树，可以获得左子树的长度，根据左子树的长度，对后续遍历分割
        vector<int> postleftTree(postOrder.begin(),postOrder.begin() + leftTree.size());
        vector<int> postrightTree(postOrder.begin() + leftTree.size(),postOrder.end());
        //递归分别构建左右子树
        root->left = buildTree(leftTree,postleftTree);
        root->right = buildTree(rightTree, postrightTree);
        return root;
    }
};

模拟构建