给二叉树的前序和中序遍历,重建出该二叉树(不含重复的数字)

重建二叉树

http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6

Tnode *rebuild_tree(int *pre, int pre_left, int pre_right, int *vin, int vin_left, int vin_right)
{
        printf("pre: left-%d, right-%d, vin: left-%d, right-%d, pre-val:%d.\n", pre_left,pre_right,vin_left,vin_right, pre[pre_left]);
        if(pre_left>pre_right || vin_left>vin_right) return NULL;
        Tnode *root = (Tnode *)calloc(1, sizeof(Tnode));
        root->val = pre[pre_left];
        int mid = 0;
        for (mid=vin_left; mid<=vin_right; mid++)
        {
                if(vin[mid] == pre[pre_left])
                {
                        printf("\n****vin (pre_left-%d, mid:%d-%d).****\n", pre_left, mid, vin[mid]);
                        if (mid>vin_left)                       {
                                printf("left.");
                                //(mid-vin_left)根结点左边有几个元素
                                root->left  = rebuild_tree(pre, pre_left+1, pre_left+(mid-vin_left), vin, vin_left, mid-1);
                        }
                        if (mid<vin_right)                        {
                                printf("right.");
                                //(pre_left+(mid-vin_left))为从pre_left开始往后推这么多元素
                                root->right = rebuild_tree(pre, (pre_left+(mid-vin_left))+1, pre_right, vin, mid+1, vin_right);
                        }
                        break;
                }
        }

        return root;
}
全部评论

相关推荐

有了offer来还愿:学校不行,专业不行,学历不行,怎么找?
点赞 评论 收藏
分享
10-13 13:49
南京大学 财务
饿魔:笑死我了,你简直是个天才
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务