创建二叉树

❝

一般情况下，二叉树的遍历序列有四种，分别是「先序遍历」、「中序遍历」、「后序遍历」以及「层序遍历」。(这里不考虑「Leetcode」上面其他乱七八糟的遍历方式).一种遍历方式是没有办法确定二叉树的，需要两种遍历方式,那么是不是这四种遍历方式随便找两种都可以呢，显然不是这样，正确的遍历方式应该是下面几种组合

❞

• 「先序遍历+中序遍历」
• 「后序遍历+中序遍历」
• 「层序遍历+中序遍历」

❝

可以发现都带有「中序遍历」。事实上证明过程也比较容易，对数学比较敏感的读者，可以清楚的感觉应该用数学归纳法证明，这边不再一一赘述。下面举一个例子

❞

• 先序遍历序列为[3,9,20,15,7]
• 中序遍历序列为[9,3,15,20,7]

由遍历顺序可以知道，先序遍历第一个访问的结点必然是根结点，这里是3，那么在中序遍历序列中可以找到3，3左边的必然是根结点的左子树，3右边的为根结点的右子树下面再依次递归建立左子树跟右子树。

最终的结果如图所示

前序+中序

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    struct TreeNode *root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    if(preorderSize==0)return NULL;
    root->val=preorder[0];
    int leftLength=0,rightLength=0;
    for( leftLength=0;inorder[leftLength]!=preorder[0];leftLength++);
    rightLength=preorderSize-(1+leftLength);
    //create leftSubTree
    root->left=buildTree(preorder+1,leftLength,inorder,leftLength);
    //create rightSubTree
    root->right=buildTree(preorder+1+leftLength,rightLength,inorder+leftLength+1,rightLength);
    return root; 
}

后序+中序

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    if(postorderSize==0)
    return NULL;
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=postorder[postorderSize-1];
    int leftLength=0,rightLength=0;
    for(leftLength=0;inorder[leftLength]!=postorder[postorderSize-1];leftLength++);
    rightLength=postorderSize-1-leftLength;
    root->left=createTree(inorder,leftLength,postorder,leftLength);
    root->right=createTree(inorder+leftLength+1,rightLength,postorder+leftLength,rightLength);
    return root;

}