题目:buildTree

---

要求:

根据中序遍历和后序遍历树构造二叉树 注意事项 你可以假设树中不存在相同数值的节点

样例:

给出树的中序遍历： [1,2,3] 和后序遍历： [1,3,2] 返回如下的树：

2 / \ 1 3

算法要求:

无

解题思路:

看这里

算法如下:

vector<int> inorder; vector<int> postorder; TreeNode *build(int startA, int endA, int startB, int endB) { if (startA > endA || startB > endB) { return NULL; } TreeNode *root = new TreeNode(postorder[endA]); int headA = endA;//根节点在后序的位置 int headB = endB;//根节点在中序的位置 while (postorder[headA] != inorder[headB]) { headB--; } root->left = build(startA, headB - startB + startA - 1, startB, headB - 1); root->right = build(headB - startB + startA, endA - 1, headB + 1, endB); return root;// } TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { // write your code here this->inorder = inorder; this->postorder = postorder; return build(0, postorder.size() - 1, 0, inorder.size() - 1); }