【数据结构C/C++】根据前序中序和中序后续遍历结果生成二叉树

前序和中序遍历结果生成二叉树

（当初面试字节跳动的时候就遇到的这道题）
对于任意一颗树而言，前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。

而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

#include 
#include 

// 定义一个树
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
// 前序数组  开始位置  结束位置
// 后续数组  开始位置  结束位置
struct TreeNode* buildTree(int* preorder, int pStart, int pEnd, int* inorder, int iStart, int iEnd) {
    if (pStart == pEnd) {
        return NULL;
    }

    // 前序遍历的第一个节点就是根节点
    int rootVal = preorder[pStart];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootVal;
    root->left = NULL;
    root->right = NULL;

    int root_in_index = 0;
    // 中序遍历中第一次等于根节点的值就是左子树
    for (int i = iStart; i < iEnd; i++) {
        // 得到中序遍历中根节点的位置
        if (inorder[i] == rootVal) {
            root_in_index = i;
            break;
        }
    }

    // 得到左子树的长度
    int leftTreeLength = root_in_index - iStart;

    // 构建左右子树（前闭后开区间）
    root->left = buildTree(preorder, pStart + 1, pStart + 1 + leftTreeLength, inorder, iStart, root_in_index);
    root->right = buildTree(preorder, pStart + 1 + leftTreeLength, pEnd, inorder, root_in_index + 1, iEnd);

    return root;
}

struct TreeNode* createTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    return buildTree(preorder, 0, preorderSize, inorder, 0, inorderSize);
}

// 前序遍历
void printTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->val);
    printTree(root->left);
    printTree(root->right);
}

int main() {
    int preorder[] = {3, 9, 20, 15, 7};
    int inorder[] = {9, 3, 15, 20, 7};
    int preorderSize = sizeof(preorder) / sizeof(preorder[0]);
    int inorderSize = sizeof(inorder) / sizeof(inorder[0]);
	//合并
    struct TreeNode* root = createTree(preorder, preorderSize, inorder, inorderSize);

    printf("前序遍历结果如下: ");
    printTree(root);
    printf("\n");

    return 0;
}

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

中序遍历和后续遍历构造二叉树

中序遍历的顺序是每次遍历左孩子，再遍历根节点，最后遍历右孩子。
后序遍历的顺序是每次遍历左孩子，再遍历右孩子，最后遍历根节点。

因此根据上文所述，我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。

所以有了第一题的基础，做第二题就很快了

#include 
#include 

// 定义树节点
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* buildTree(int* inorder, int iStart, int iEnd, int* postorder, int pStart, int pEnd) {
    if (iStart > iEnd || pStart > pEnd) {
        return NULL;
    }

    // 在后序遍历序列中，最后一个元素是树的根节点
    int rootVal = postorder[pEnd];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootVal;
    root->left = NULL;
    root->right = NULL;

    int rootIndex = -1;
    // 在中序遍历序列中，根节点的左边是左子树，右边是右子树
    for (int i = iStart; i <= iEnd; i++) {
        if (rootVal == inorder[i]) {
            rootIndex = i;
            break;
        }
    }

    int leftTreeNum = rootIndex - iStart;
    root->left = buildTree(inorder, iStart, rootIndex - 1, postorder, pStart, pStart + leftTreeNum - 1);
    root->right = buildTree(inorder, rootIndex + 1, iEnd, postorder, pStart + leftTreeNum, pEnd - 1);

    return root;
}

struct TreeNode* createTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    return buildTree(inorder, 0, inorderSize - 1, postorder, 0, postorderSize - 1);
}

// Helper function to print the tree (for testing)
void printTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->val);
    printTree(root->left);
    printTree(root->right);
}

int main() {
    int inorder[] = {9, 3, 15, 20, 7};
    int postorder[] = {9, 15, 7, 20, 3};
    int inorderSize = sizeof(inorder) / sizeof(inorder[0]);
    int postorderSize = sizeof(postorder) / sizeof(postorder[0]);

    struct TreeNode* root = createTree(inorder, inorderSize, postorder, postorderSize);

    printf("前序遍历: ");
    printTree(root);
    printf("\n");

    return 0;
}

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

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。