LeetCode 106. 从中序与后序遍历序列构造二叉树

���路解析可以看这里

（）

---

主要注意在切割数组时要结合vector构造函数的左闭右开性质，不要混淆。

class Solution {public:    TreeNode* buildTree(vector& inorder, vector& postorder) {        if(postorder.size() == 0)       return NULL;                int rootVal = postorder[postorder.size() - 1];        TreeNode* root = new TreeNode(rootVal);             //自己构建新树        if(postorder.size() == 1)       return root;                auto iter = find(inorder.begin(), inorder.end(), rootVal);         int pivot = iter - inorder.begin();     //找到根结点在中序数组的下标，作为后续分割依据                //切割中序数组，将这层inorder的两个子序列传给下一层        vector leftInOrder(inorder.begin(), inorder.begin() + pivot);     //左边[)        vector rightInOrder(inorder.begin() + pivot + 1, inorder.end());  //右边(]        //切割后序数组，将这层postorder的两个子序列传给下一层        //pivot也反映了左子树的结点数——>有以下的数量关系        vector leftPostOrder(postorder.begin(), postorder.begin() + pivot);        vector rightPostOrder(postorder.begin() + pivot, postorder.end() - 1);        root -> left = buildTree(leftInOrder, leftPostOrder);        root -> right = buildTree(rightInOrder, rightPostOrder);        return root;    }};

（）