From 劍指Offer 何海濤 著

#include <iostream> #include <exception> #include <string>struct BinaryTreeNode {int m_nValue;BinaryTreeNode *m_pLeft;BinaryTreeNode *m_pRight; };BinaryTreeNode* ConstructBinaryTree(const int *preOrder, const int *inOrder, int length) {if(preOrder== NULL || inOrder == NULL || length <= 0) {return NULL;}BinaryTreeNode *root = new BinaryTreeNode;root->m_nValue = *preOrder;const int *rootInOrder = inOrder;while(rootInOrder < inOrder+length && *rootInOrder != *preOrder) {rootInOrder++;}if(rootInOrder == inOrder+length) {throw std::exception();}int leftLength = rootInOrder-inOrder;root->m_pLeft = ConstructBinaryTree(preOrder+1, inOrder, leftLength);root->m_pRight = ConstructBinaryTree(preOrder+leftLength+1, rootInOrder+1, length-leftLength-1);return root; }

測試集:

bool isEqual(const BinaryTreeNode *left, const BinaryTreeNode *right) {if(left == NULL && right == NULL) {return true;}if(left != NULL && right != NULL) {return left->m_nValue == right->m_nValue && isEqual(left->m_pLeft, right->m_pLeft) && isEqual(left->m_pRight, right->m_pRight);} }void FreeBinaryTree(BinaryTreeNode *root) {if(root != NULL) {FreeBinaryTree(root->m_pLeft);FreeBinaryTree(root->m_pRight);delete root;} }void test(const int *preOrder, const int *inOrder, int length, const BinaryTreeNode *expected) {BinaryTreeNode *actual = ConstructBinaryTree(preOrder, inOrder, length);std::cout << std::boolalpha << (isEqual(actual, expected)) << std::endl;FreeBinaryTree(actual); }int main(int argc, char* argv[]) {{// 普通二叉樹// 1// / \// 2 3// / / \// 4 5 6// \ /// 7 8int preOrder[] = {1, 2, 4, 7, 3, 5, 6, 8};int inOrder[] = {4, 7, 2, 1, 5, 3, 8, 6};BinaryTreeNode node8;node8.m_nValue = 8;node8.m_pLeft = NULL;node8.m_pRight = NULL;BinaryTreeNode node7;node7.m_nValue = 7;node7.m_pLeft = NULL;node7.m_pRight = NULL;BinaryTreeNode node6;node6.m_nValue = 6;node6.m_pLeft = &node8;node6.m_pRight = NULL;BinaryTreeNode node5;node5.m_nValue = 5;node5.m_pLeft = NULL;node5.m_pRight = NULL;BinaryTreeNode node4;node4.m_nValue = 4;node4.m_pLeft = NULL;node4.m_pRight = &node7;BinaryTreeNode node3;node3.m_nValue = 3;node3.m_pLeft = &node5;node3.m_pRight = &node6;BinaryTreeNode node2;node2.m_nValue = 2;node2.m_pLeft = &node4;node2.m_pRight = NULL;BinaryTreeNode node1;node1.m_nValue = 1;node1.m_pLeft = &node2;node1.m_pRight = &node3;test(preOrder, inOrder, 8, &node1);}{// 所有結點都沒有右子結點// 1// /// 2// /// 3// /// 4// /// 5int preOrder[] = {1, 2, 3, 4, 5};int inOrder[] = {5, 4, 3, 2, 1};BinaryTreeNode node5;node5.m_nValue = 5;node5.m_pLeft = NULL;node5.m_pRight = NULL;BinaryTreeNode node4;node4.m_nValue = 4;node4.m_pLeft = &node5;node4.m_pRight = NULL;BinaryTreeNode node3;node3.m_nValue = 3;node3.m_pLeft = &node4;node3.m_pRight = NULL;BinaryTreeNode node2;node2.m_nValue = 2;node2.m_pLeft = &node3;node2.m_pRight = NULL;BinaryTreeNode node1;node1.m_nValue = 1;node1.m_pLeft = &node2;node1.m_pRight = NULL;test(preOrder, inOrder, 5, &node1);}{// 所有結點都沒有左子結點// 1// \// 2// \// 3// \// 4// \// 5int preOrder[] = {1, 2, 3, 4, 5};int inOrder[] = {1, 2, 3, 4, 5};BinaryTreeNode node5;node5.m_nValue = 5;node5.m_pLeft = NULL;node5.m_pRight = NULL;BinaryTreeNode node4;node4.m_nValue = 4;node4.m_pLeft = NULL;node4.m_pRight = &node5;BinaryTreeNode node3;node3.m_nValue = 3;node3.m_pLeft = NULL;node3.m_pRight = &node4;BinaryTreeNode node2;node2.m_nValue = 2;node2.m_pLeft = NULL;node2.m_pRight = &node3;BinaryTreeNode node1;node1.m_nValue = 1;node1.m_pLeft = NULL;node1.m_pRight = &node2;test(preOrder, inOrder, 5, &node1);}{// 樹中只有一個結點int preOrder[] = {1};int inOrder[] = {1};BinaryTreeNode node1;node1.m_nValue = 1;node1.m_pLeft = NULL;node1.m_pRight = NULL;test(preOrder, inOrder, 1, &node1);}{// 完全二叉樹// 1// / \// 2 3// / \ / \// 4 5 6 7int preOrder[] = {1, 2, 4, 5, 3, 6, 7};int inOrder[ ] = {4, 2, 5, 1, 6, 3, 7};BinaryTreeNode node7;node7.m_nValue = 7;node7.m_pLeft = NULL;node7.m_pRight = NULL;BinaryTreeNode node6;node6.m_nValue = 6;node6.m_pLeft = NULL;node6.m_pRight = NULL;BinaryTreeNode node5;node5.m_nValue = 5;node5.m_pLeft = NULL;node5.m_pRight = NULL;BinaryTreeNode node4;node4.m_nValue = 4;node4.m_pLeft = NULL;node4.m_pRight = NULL;BinaryTreeNode node3;node3.m_nValue = 3;node3.m_pLeft = &node6;node3.m_pRight = &node7;BinaryTreeNode node2;node2.m_nValue = 2;node2.m_pLeft = &node4;node2.m_pRight = &node5;BinaryTreeNode node1;node1.m_nValue = 1;node1.m_pLeft = &node2;node1.m_pRight = &node3;test(preOrder, inOrder, 7, &node1);}{int preOrder[] = {1, 2, 4, 5, 3, 6, 7};int inOrder[] = {4, 2, 8, 1, 6, 3, 7};try {test(preOrder, inOrder, 7, NULL);} catch(std::exception& e) {std::cout << "true" << std::endl;}}{test(NULL, NULL, 0, NULL);}return 0;}

?

轉載于:https://www.cnblogs.com/long3216/p/4439448.html

總結

以上是生活随笔為你收集整理的{面试题6: 重建二叉树}的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。