先序 + 中序 恢复二叉树

void createBinaryTree(BintreeNode *& t, char * preorder, char * inorder, int n)
{
    if (n == 0)
    {
        t = NULL;
    }
    else
    {
        int k = 0;
        while (preorder[0] != inorder[k])
        {
            ++ k;
        }
        t = (BintreeNode *)malloc(sizeof(BintreeNode));
        assert(t != NULL);
        t->data = inorder[k];
        createBinaryTree(t->leftChild, preorder + 1, inorder, k);
        createBinaryTree(t->rightChild, preorder + k + 1, inorder + k + 1, n - k - 1);
        cout << t->data << endl;
    }
    return ;
}

1、当前取出，必定是当前子树先序遍历数组的开头，即第一个数preorder[0]。
2、由于可以使用第四个参数n来说明子树中节点的个数，所以递归的过程中，要么没有节点，要么有节点。而有节点必定能在while的过程中找出当前子树inorder中序数组范围内的preorder[0]值。
3、不管是左子树还是右子树的递归，第一个参数就是指向[左|右]孩子的指针，第二参数就是指向当前节点的[左|右]子树在先序数组的开头，第三个参数就是指向当前节点的[左|右]子树在中序数组的开头，第四个参数就是说明[左|右]子树的节点个数。

按照上面的规定，不停的递归，就能通过先序 + 中序恢复二叉树。

中序 + 后序 恢复二叉树

void createBinaryTree(BintreeNode *& t, char *postorder, char *inorder, int n)
{
    if (n == 0)
    {
        t = NULL;
    }
    else
    {
        int  k = 0;
        while (postorder[n - 1] != inorder[k])
        {
            ++ k;
        }
        t = (BintreeNode *)malloc(sizeof(BintreeNode));
        // 断言，即为传给assert的参数是0的话，就会报错&&终止程序！（避免由程序运行引起更大的错误） 
        assert(t != NULL);
        t->data = inorder[k];
        cout << t->data << endl;
        createBinaryTree(t->leftChild, postorder, inorder, k);
        createBinaryTree(t->rightChild, postorder + k, inorder + k + 1, n - k - 1);
    }
}

1、当前取出，必定是当前子树的后序遍历数组的最后一个数即postorder[n - 1]。
2、由于可以使用第四个参数n来说明子树中节点的个数，所以递归的过程中，要么没有节点，要么有节点。而有节点必定能在while的过程中找出当前子树inorder中序数组范围内的postorder[n - 1]值。
3、不管是左子树还是右子树的递归，第一个参数就是指向[左|右]孩子的指针，第二参数就是指向当前节点的[左|右]子树在后序数组的开头，第三个参数就是指向当前节点的[左|右]子树在中序数组的开头，第四个参数就是说明[左|右]子树的节点个数。

按照上面的规定，不停的递归，就能通过中序 + 后序恢复二叉树。

Note:没有中序遍历，就没法恢复二叉树。

PS:通过这次二叉树恢复的学习，算是又一次加强我对递归的学习能力，也吸取了教训。即要想先了解这一个递归，应该先找出每次递归的共同点，归纳其的性质。如果能够验证通过归纳的性质，验证这个递归的可行性，无疑是极好的。如果还是不理解，那就拿起笔，自己递归一遍试试。