由中序序列和先序序列确定一颗二叉树

递归创建二叉树

preSq为前序序列；inSq为中序序列；l1、h1分别为前序序列的第一个结点值和最后一个结点值；l2、h2分别为中序序列的第一个结点值和最后一个结点值

BinaryTree create(int preSq[], int inSq[], int l1, int h1, int l2, int h2){
    auto root = new TreeNode;
    root->data = preSq[l1];
    int i = l2, lLen, rLen;
    for(;inSq[i] != root->data; i++); //查找根结点
    lLen = i - l2;
    rLen = h2 - i;
    if(lLen){//递归遍历左子树
        p->lChild = create(preSq, inSq, l1 + 1, lLen + l1, l2, lLen + l2 - 1);
    }
    if(rLen){
            p->rChild = create(preSq, inSq, h1 - rLen + 1, h1, h2 - rlen + 1, h2);
    }
    return root;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接