[LeetCode]Construct Binary Tree from Inorder and Postorder T

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

这道题与上一题类似， 要求根据二叉树的后序遍历序列和中序遍历序列构建二叉树。后序遍历序列的末尾是根节点，在中序遍历序列中找出这个根节点root，则root两边就是其左右子树。然后根据左右子树的个数，确定后序遍历的左右子树的分界。关键分界点找到之后就可以进行递归了。

下面贴上代码：

/** * Definition for binary tree * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {return build(inorder, 0, inorder.size(), postorder, 0, postorder.size());}TreeNode* build(vector<int>& inorder, int ileft, int iright, vector<int>& postorder, int pleft, int pright){if (ileft == iright){return NULL;}int i = 0;while (postorder[pright – 1] != inorder[i])i++;TreeNode* tn = new TreeNode(inorder[i]);tn->left = build(inorder, ileft, i, postorder, pleft, pleft + i – ileft);tn->right = build(inorder, i + 1, iright, postorder, pleft + i – ileft, pright – 1);return tn;}};

，打掉的应是脆弱的铁屑，锻成的将是锋利的钢刀。