面接試験問題6:二叉樹を再建する

テーマリンク:http://ac.jobdu.com/problem.php?pid=1385
考え方:前の順序で結果の最初の数字がルートノードであり、中の順でルートノードの位置を確認すると、左の位置が左のサブツリーの中の順序で巡回した結果になります.明らかに私たちは簡単に左右の子木の前の順序と中の順序を経て結果を得ることができます.再帰的に構築するために使用することができます.
豆知識:
preorder 前のシーケンス
インディーズ   シーケンス
postored後シーケンス
コード:

 1 #include <cstdio>

 2 using namespace std;

 3 const int MAXN = 1005;

 4 struct BinaryTreeNode

 5 {

 6     int             nValue;

 7     BinaryTreeNode* nLeft;

 8     BinaryTreeNode* nRight;

 9 };

10  

11 bool flag = true;  //         

12  

13 BinaryTreeNode* BuildTree(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)

14 {

15     if (flag == false) return NULL;

16     int rootValue = startPreorder[0];

17     BinaryTreeNode* root = new BinaryTreeNode();

18     root->nValue = rootValue;

19     root->nLeft = root->nRight = NULL;

20  

21     //       

22     if (startPreorder == endPreorder)

23     {

24         if (startInorder == endInorder && *startPreorder == *startInorder) return root;

25         else

26         {

27             flag = false;

28             return NULL;

29         }

30     }

31     //            

32     int* rootInder = startInorder;

33     while (rootInder <= endInorder && *rootInder != rootValue) ++rootInder;

34     //       

35     if (rootInder == endInorder && *rootInder != rootValue)

36     {

37         flag = false;

38         return NULL;

39     }

40     int leftLength = rootInder - startInorder;

41     int* leftPreorderEnd = startPreorder + leftLength;

42     if (leftLength > 0)

43     {

44         //      

45         root->nLeft = BuildTree(startPreorder + 1, leftPreorderEnd, startInorder, rootInder - 1);

46     }

47     if (leftLength < endPreorder - startPreorder)

48     {

49         //      

50         root->nRight = BuildTree(leftPreorderEnd + 1, endPreorder, rootInder + 1, endInorder);

51     }

52     return root;

53 }

54  

55 void postorderTravel(BinaryTreeNode* root)

56 {

57     //     

58     if (root != NULL)

59     {

60         postorderTravel(root->nLeft);

61         postorderTravel(root->nRight);

62         printf("%d ", root->nValue);

63     }

64 }

65  

66 int main()

67 {

68     int preOrder[MAXN];

69     int inOrder[MAXN];

70     int n;

71     while (scanf("%d", &n) != EOF)

72     {

73         for (int i = 0; i < n; ++i) scanf("%d", &preOrder[i]);

74         for (int i = 0; i < n; ++i) scanf("%d", &inOrder[i]);

75         flag = true;

76         BinaryTreeNode* root = BuildTree(preOrder, preOrder + n - 1, inOrder, inOrder + n - 1);

77         if (flag == false) printf("No");

78         else postorderTravel(root);

79         printf("
");

80     }

81     return 0;

82 }