【剑指offer】面试题6：重建二叉树

2019-11-06 07:49:32

字体：大中小

来源：转载

供稿：网友

//题目：输入二叉树的前序遍历和后序遍历的结果，请重新构建出该二叉树。假设输入的前序遍历和后序遍历的结果都不含重复的数字。//二叉树的定义#include<iostream>struct BinaryTreeNode{ int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_PRight;};BinaryTreeNode* construct(int *preorder, int*inorder, int length){ if (preorder == NULL || inorder == NULL) { return NULL; } return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);}BinaryTreeNode* ConstructCore( int *startPreorder, int *endPreorder, int *startInorder, int *endInorder){ //前序遍历的第一个数字是根节点的值 int rootValue = startPreorder[0]; BinaryTreeNode*root = new BinaryTreeNode(); root->m_nValue = rootValue; root->m_pLeft = root->m_pRight = NULL; if (startPreorder == endPreorder) { if (startInorder == endInorder&&*startPreorder == *startInorder) { return root; } else { throw std:: exception("Invalid input."); } } //在中序遍历中找到根结点的值 int *rootInorder = startInorder; while (rootInorder <= endInorder&&*rootInorder != rootValue) { ++rootInorder; } if (rootInorder == endInorder&&*rootInorder != rootValue) { throw std::exception("Invalid input."); } int leftLength = rootInorder - startInorder; int *leftPreorderEnd = startPreorder + leftLength; if (leftLength > 0) { //构建左子树 root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);//前序遍历的第一个结点作为了根节点，故+1 } if (leftLength < endPreorder - startPreorder)//左子树建完，发现个数不匹配，那肯定就是要建右子树了 { //构建右子树 root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder); }}

上一篇：Dijkstra算法模版洛谷P1339 [USACO09OCT]热浪Heat Wave

下一篇：单片机实现数组先进先出

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注