先序遍历序列+中序遍历序列构建二叉树

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

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

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

#include
#include
#include
 struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
 };

 struct TreeNode *PreInCreat(int *, int *, int, int, int, int);
 struct TreeNode *buildTree(int *, int, int *, int);
 void PreTraverse(struct TreeNode *);
 void InOrderTraverse(struct TreeNode *);

 int main(void){
     int preorder[5] = {3, 9, 20, 15, 7};
     int inorder[5]= {9, 3, 15, 20, 7};
     struct TreeNode *root = buildTree(preorder, 5, inorder, 5);
     printf("<-------先序遍历------->");
     PreTraverse(root);
     printf("<-------中序遍历------->");
     InOrderTraverse(root);
     return 0;
 }

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

/**
 * @param preorder 先序遍历序列数组
 * @param inorder  中序遍历序列数组
 * @param preorder_left 先序遍历序列左边界
 * @param preorder_right 先序遍历序列右边界
 * @param inorder_left 中序遍历序列左边界
 * @param inorder_right 中序遍历序列右边界
 */
struct TreeNode *PreInCreat(int *preorder, int *inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
    if (preorder_left > preorder_right) {
        return NULL;
    }
    //先序遍历的第一个节点就是根节点
    int preorder_root = preorder_left;
    //在中序遍历序列中查找根节点「preorder_root」的下标序号
    int inorder_root;
    for (inorder_root = inorder_left; inorder[inorder_root] != preorder[preorder_root]; inorder_root++);
    //创建根节点
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = preorder[preorder_root];
    // 得到左子树中的节点数目
    int size_left_subtree = inorder_root - inorder_left;
    // 递归地构造左子树，并连接到根节点
    // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
    root->left = PreInCreat(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
    // 递归地构造右子树，并连接到根节点
    // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
    root->right = PreInCreat(preorder, inorder, preorder_left + 1 + size_left_subtree, preorder_right, inorder_root + 1, inorder_right);
    return root;
}

void PreTraverse(struct TreeNode *P)
{
    if(P!=NULL){
        printf("%d\t", P->val);
        PreTraverse(P->left);
        PreTraverse(P->right);
    }
}

void InOrderTraverse(struct TreeNode *P)
{
    if(P!=NULL){
        InOrderTraverse(P->left);
        printf("%d\t", P->val);
        InOrderTraverse(P->right);
    }
}
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

参考：

作者：wang_ni_ma
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/dong-hua-yan-shi-105-cong-qian-xu-yu-zhong-xu-bian/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。