通过二叉树的中序和后序遍历序列构造二叉树（非递归）

题目：通过二叉树的中序和后序遍历序列构造二叉树

同样，使用分治法来实现是完全可以的，可是在LeetCode中运行这种方法的代码，总是会报错：

Memory Limit Exceeded

与用先序和后序遍历构造二叉树的方法类似，但还是要做一些改变：

如果从后往前处理中序和后序的序列，则处理就为如下所示的情况：

Reverse_PZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Q6ILj5oarT0tfTyvehqtfz19PK9zxicj4KUmV2ZXJzZV9Jbjog09LX08r3oaq4+aGq1/PX08r3PC9wPgo8cD48L3A+CjxpbWcgc3JjPQ=="" alt="\">
这样处理方式和先序―中序就差不多了，只是将添加左孩子的情况，改为添加右孩子，反之依然。 实现代码如下所示：

TreeNode *buildTree_in_post(vector
  
    &inorder, vector
   
     &postorder) { stack
    
      s; int len = (int) inorder.size(); if(len == 0) return NULL; int in_ptr, post_ptr;//分别用于对中序和后序处理 in_ptr = post_ptr = len-1;//从序列最后一个元素往前进行处理 TreeNode* root = new TreeNode(postorder[post_ptr]);//构造根结点,后序遍历最后一个元素为根结点的值 TreeNode* pCur = root;//用于保存树当前处理结点 int flag = 0;//用于决定是否构造左结点 post_ptr--; s.push(root); while(post_ptr > -1)//处理到pOstorder[0] { if(!s.empty() && s.top()->val == inorder[in_ptr]) { pCur = s.top(); s.pop(); in_ptr--; flag = 1; } else { if(flag == 1)//构造左结点 { pCur->left = new TreeNode(postorder[post_ptr]); pCur = pCur->left; s.push(pCur); post_ptr--; flag = 0; } else//构造右结点 { pCur->right = new TreeNode(postorder[post_ptr]); pCur = pCur->right; s.push(pCur); post_ptr--; } } } return root; }