LeetCode Construct Binary Tree from Inorder and Postorder Traversal 思考分析过程分享

Note:

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

利用二叉树的中序和后序的序列还原一颗二叉树。

Note的意思是如果有节点的值是重复的话，那么就无法确保这颗二叉树是唯一的了。

一开始我基本上是毫无头绪。然后思考：

1 画图： 把二叉树和其中序和后序的序列都画出来（这个很重要，我以前有时候总是凭空想象，结果脑子一片空白）

2 把问题写下来：怎么构造一个节点？用什么算法？能用递归吗？从什么地方开始构造？根节点？反正能想到的问题都写下来。一定要写下来！

3 观察：到底有什么特点是可以利用来解题的呢？ A）后序最后一个一定是根节点 B）中序第一个一定是最左边的根节点。C）根节点左右子树是可以分开的

那么什么特点是有用的呢？A）C）是有用的；B）好像是无用的。

利用A）C）可以构造递归，每递归一次可以构造一个节点。

做起来又发现很多“小问题”：

1）每个节点必须用new动态分配内存，因为不能返回局部函数指针地址

2）利用C）特性分开左右子树很麻烦，因为要维持4个边界，这样的情况要极其小心，因为很容易下标越界等问题出来的。最好写个更小的程序，先验证过下标处理正确之后再调用该函数。（这个非常麻烦！每次需要打起12分精神）

3）递归参数如何处理？一开始我是想剪裁vector，每次把新的vector装的中序和后序数列递归传递给下一个递归函数，但是这样就会造成大量的参数传递，是个非常糟糕的做法。程序能运行也很糟糕。千万不能用vector作参数递归调用。应该是使用其下标，每次用下标标明需要vector中的哪一部分进行运算！

4）特殊情况处理，4个边界处理，空树，树为一个根节点。

感觉好辛苦，一个 编程任务，如临大敌似的！不知道是不是功力不到。

突然想到这是不就像是金庸武功第一层境界：举重若重。

不知道别人是不是到了第二层境界了：举重若轻

第三层境界：举轻若重！

最后：摘叶飞花！

struct TreeNode {  
    int val;  
    TreeNode *left;  
    TreeNode *right;  
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};  
  
class Solution {  
public:  
    TreeNode *buildTree(vector &inorder, vector &postorder)   
    {         
        return split(inorder, 0, inorder.size(), postorder, 0, postorder.size());  
    }  
  
    TreeNode *split(vector &in, int inbeg,int inend, vector& po, int pobeg, int poend)  
    {  
        if(in.empty()) return nullptr;  
        TreeNode *node = new TreeNode(po[poend-1]);  
        if(in.size() <= 1) return node;  
  
        auto initer = find(in.begin()+inbeg, in.begin()+inend, po[poend-1]);  
        int lnum = initer - in.begin() - inbeg;  
        int rnum = inend - inbeg - lnum - 1;  
  
        int linbeg = inbeg;  
        int linend = inbeg + lnum;  
        int rinbeg = inbeg + lnum + 1;  
        int rinend = inend;  
  
        int lpobeg = pobeg;  
        int lpoend = pobeg + lnum;  
        int rpobeg = pobeg + lnum;  
        int rpoend = poend - 1;  
  
        if(linbegleft = split(in, linbeg, linend, po, lpobeg, lpoend);  
        if(rinbegright = split(in, rinbeg, rinend, po, rpobeg, rpoend);  
  
        return node;  
    }  
};  

测试程序：

#include  
#include  
  
using namespace std;  
  
void printTree(TreeNode *root)  
{  
    if(!root) return;  
    cout<val<<" ";  
    printTree(root->left);  
    printTree(root->right);  
}  
  
  
int main()  
{  
    TreeNode *root;  
    TreeNode *re;  
    int a[] = {8,4,2,5,1,6,3,7};  
    int b[] = {8,4,5,2,6,7,3,1};  
    vector li(a, a+8);  
    vector ri(b, b+8);  
    Solution solu;  
  
    root = solu.buildTree(li,ri);  
  
    printTree(root);  
    cout<