剑指Offer面试题:5.重建二叉树

一题目:重建二叉树二思路先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:5.重建二叉树此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:重建二叉树

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示的二叉树并输出它的头结点。

         
剑指Offer面试题:5.重建二叉树

二 思路

  先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后,就可以递归地去分别构建它的左右子树。

三 代码实现

(1)索引实现

struct TreeNode
{
    int data;
    TreeNode* pLeft;
    TreeNode* pRight;
};

// 重构二叉树
TreeNode* RebulidTree(int *pre, int *mid, int len)
{
    if(NULL == pre || NULL == mid || len < 0)
    {
        return NULL;
    }
    // 根据前序遍历得到根节点
    int root = pre[0];
    TreeNode *pNode = new TreeNode;
    pNode->data = root;
    pNode->pLeft = pNode->pRight = NULL;
    
    int i = 0;
    // 根据根节点将中序遍历结果分成左子树和右子树,前提肯定能找到
    for (; i < len;i ++)
    {
        if (root == mid[i])
        {
            break;
        }
    }
    if (i > 0)
    {
        int *midleft = new int[i];
        memcpy(midleft, mid, sizeof(int) * i);
        int *preleft = new int[i];
        memcpy(preleft, &pre[1], sizeof(int)*i);
        pNode->pLeft = RebulidTree(preleft, midleft, i);
        delete[] midleft;
        delete[] preleft;
    }
    if (i < len-1)
    {
        int *midright = new int[len - i - 1];
        // 将中序分配左子树,右子树
        memcpy(midright, &mid[i+1], sizeof(int)*(len-i-1));
        // 将前序分配左子树和右子树
        int *preright = new int[len-i-1];
        memcpy(preright, &pre[i + 1], sizeof(int)*(len-i-1));
        pNode->pRight = RebulidTree(preright, midright, len - i - 1);
        delete[] midright;
        delete[] preright;
    }
    
    return pNode;
}

(2)指针实现

struct TreeNode
{
    int data;
    TreeNode* pLeft;
    TreeNode* pRight;
};

TreeNode* StructNode(int *StartPre, int *EndPre, int *StartMid, int *EndMid)
{
    // 根据前序遍历得到根节点
    int nRootValue = StartPre[0];
    TreeNode *pNode = new TreeNode;
    pNode->data = nRootValue;
    pNode->pLeft = pNode->pRight = NULL;

    if (StartPre == EndPre)
    {
        if ((StartMid == EndMid) && (*StartPre == *StartMid))
        {
            return pNode;
        }
        else
        {
            throw std::exception("Invalid input");
        }
    }
    // 在中序遍历中找到根结点的值
    int *RootMid = StartMid;
    while(RootMid < EndMid && *RootMid != nRootValue)
    {
        RootMid ++;
    }
    // 若没找到,抛出异常
    if(RootMid == EndMid && *RootMid != nRootValue)
    {
        throw std::exception("Invalid input");
    }

    int nLeftLength = RootMid - StartMid;
    int *LeftPreEnd = StartPre+nLeftLength;
    if (nLeftLength > 0)
    {
        pNode->pLeft = StructNode(++StartPre, LeftPreEnd, StartMid, RootMid-1);
    }
    if (nLeftLength < EndMid - StartMid)
    {
        pNode->pRight = StructNode(LeftPreEnd+1, EndPre,  RootMid+1, EndMid);
    }
    return pNode;
}

TreeNode* RebulidTree_2 (int *pre, int *mid, int len)
{
    if(NULL == pre || NULL == mid || len < 0)
    {
        return NULL;
    }

    return StructNode(pre, pre + len -1, mid, mid+len-1);
}

void main()
{
    int pre[] = {1,2,4,7,3,5,6,8};
    int mid[] = {4,7,2,1,5,3,8,6};

    TreeNode* p =RebulidTree_2(pre, mid, 8);
    return;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120170.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号