大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
一 题目：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示的二叉树并输出它的头结点。
二 思路
先根据前序遍历序列的第一个数字创建根结点，接下来在中序遍历序列中找到根结点的位置，这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后，就可以递归地去分别构建它的左右子树。
三 代码实现
（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; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120170.html原文链接：https://javaforall.net
