问题描述

给定一棵二叉树的前序遍历和后序遍历，给出一种可能的中序遍历结果

输入示例：

A B D C E

D B E C A

输出示例：

一种可能的中序遍历结果为：D B A E C

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
  struct TreeNode* left;  
  struct TreeNode* right;  
  char  elem;  
} TreeNode;

/**
 * 截取s字符串子串 n <= x <= m
 */
char * getString(char * s, int n, int m) {
    n ++;
    m ++;
    char *r = (char *) malloc(sizeof(char) * (m - n));
    s = s + (n - 1);
    for(int i = 0; i < m - (n - 1); i ++) {
        r[i] = s[i];
    }
    return r;
}

// 递归中序遍历
// 定义中序遍历结果为全局变量 结果保存到 inorder中
int tempIndex = 0;
char *inorder;
void inTree(TreeNode *tree) {
    if(tree != NULL) {
        // left
        inTree(tree->left);

        printf(" %c ", tree->elem);
        if(tempIndex == 0) {
            inorder = (char *) malloc(sizeof(char));
        } else {
            inorder = (char *) realloc(inorder, sizeof(char)*(tempIndex+1));
        }
        inorder[tempIndex] = tree->elem;
        tempIndex ++;
        // printf(" --%c-- ", inorder[tempIndex]);
        //right
        inTree(tree->right);
    }
    // printf("\n---%d-----\n", tempIndex);
}
/**
 * 由先序 后序构造树
 */
TreeNode * buildTree(char* preorder, char* postorder){
    // 如果长度为 1 证明没有孩子
    if(strlen(preorder) == 1 || strlen(postorder) == 1) {
        // printf("%c ", preorder[0]);
        TreeNode * r = (TreeNode *) malloc(sizeof(TreeNode));
        r->elem = preorder[0];
        return r;
    }

    TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));
    // 第一个为根节点
    node->elem = preorder[0];

    //左右子数都有, 先序第二个元素为左子树根
    if(preorder[1] != postorder[strlen(postorder) - 2]) {
        // m左子树长度 n左子树根
        int m=0, n=1;
        for(int i=0; i<strlen(postorder); i++) {
            if(preorder[1] == postorder[i]) {
                m = i + 1;
            }
        }
        // 左子树先后序
        printf("左子树先后序:\n");
        printf("---%s----\n", getString(postorder, 0, m-1));
        printf("---%s----\n", getString(preorder, n, m));
        // 右子数先后序
        printf("右子树先后序:\n");
        printf("---%s----\n", getString(preorder, m+1, strlen(preorder)-1));
        printf("---%s----\n", getString(postorder, m, strlen(postorder) - 2));

        //递归
        node->left = buildTree(getString(preorder, n, m),getString(postorder, 0, m-1));
        // printf("%c ", preorder[0]);
        node->right = buildTree(getString(preorder, m+1, strlen(preorder)-1),getString(postorder, m, strlen(postorder) - 2));
    } else { //只有左子数
        node->left = buildTree(getString(preorder, 1, strlen(preorder)-1),getString(postorder, 0, strlen(postorder) - 2));
        node -> right = NULL;
    }

    return node;
}

int main() {
    char *pr = "ABDGHECKFIJ";
    char *po = "GHDEBKJIFCA";
    TreeNode * t = buildTree(pr,po);
    printf("\n\n中序遍历结果为:");
    inTree(t);
    printf("\n");
    return 0;
}