①与“已知后序中序，求先序”一样的左右递归方法（分而治之）
/*** Definition for a binary tree node.* 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 pre(postorder.size()-1, 0, inorder.size()-1, inorder, postorder);}TreeNode* pre(int rootpo, int startin, int endin, vector<int>& inorder, vector<int>& postorder){ //子树根结点在postorder[]中的下标，子树在inorder[]中的起点和终点if(startin>endin) return NULL;int root=postorder[rootpo];int rootin=startin; //在inorder[start~end]中找到rootin（根结点在中序遍历中的下标）while(rootin<endin&&inorder[rootin]!=root){rootin++;}TreeNode* node=new TreeNode(root);int leftrootpo=rootpo-(endin-rootin)-1; //右子树：endin~rootin，所以左子树在postorder[]的下标=rootpo-右子树-1int leftstartin=startin; //左子树在inorder[]中的起点和终点int leftendin=rootin-1;node->left=pre(leftrootpo, leftstartin, leftendin, inorder, postorder);int rightrootpo=rootpo-1;int rightstartin=rootin+1;int rightendin=endin;node->right=pre(rightrootpo, rightstartin, rightendin, inorder, postorder);return node;}
};
②*****迭代法，原理？？？