重建二叉树

/_src/c/binary-tree/rebuild/rebuild.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
/**
 * rebuild binary tree from inorder and preorder sequence
 **/
struct binary_tree_node *
rebuild_binary_tree_pre(int n, int inOrderSeq[], int preOrderSeq[])
{
    // root value
    int value = preOrderSeq[0];

    // count left subtree nodes
    int lefts = n;
    for (int i=0; i<n; i++) {
        if (inOrderSeq[i] == value) {
            lefts = i;
            break;
        }
    }

    // bad seq
    if (lefts == n) {
        return NULL;
    }

    // calculate right subtree nodes
    int rights = n - 1 - lefts;

    struct binary_tree_node *left = NULL;
    struct binary_tree_node *right = NULL;

    // rebuild left subtree recursively
    if (lefts > 0) {
        left = rebuild_binary_tree_pre(lefts, inOrderSeq, preOrderSeq+1);
        if (left == NULL) {
            return NULL;
        }
    }

    // rebuild left subtree recursively
    if (rights > 0) {
        right = rebuild_binary_tree_pre(rights, inOrderSeq+lefts+1, preOrderSeq+lefts+1);
        if (right == NULL) {
            free_tree(left);
            return NULL;
        }
    }

    // allocate memory for root node
    struct binary_tree_node *root = (struct binary_tree_node *)malloc(sizeof(struct binary_tree_node));
    if (root == NULL) {
        free_tree(left);
        free_tree(right);
        return NULL;
    }

    // set root node fields
    root->value = value;
    root->left= left;
    root->right = right;

    return root;
}