aboutsummaryrefslogtreecommitdiff
path: root/construct_bt_pre_post_trav.c
blob: 63eb9a969a49dcc04e56408c6f4235fb1b63dabb (plain)
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
// 889. Construct Binary Tree from Preorder and Postorder Traversal
#include "leetcode.h"

/*
 * given two integer array, 'preorder' and 'postorder' where 'preorder' is the
 * preorder traversal of a binary tree of distinct values and 'postorder' is the
 * postorder traversal of the same tree, reconstruct and return the binary tree.
 * if there exists multiple answers, you can return any of  them.
 */

struct TreeNode *constructFromPrePost(int *preorder, int preorderSize,
                                      int *postorder, int postorderSize) {
  struct TreeNode *ans = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  ans->val = *preorder;
  ans->left = ans->right = 0;
  if (preorderSize == 1)
    return ans;
  int val = postorder[postorderSize - 2], i;
  for (i = 1; preorder[i] ^ val; ++i)
    ;
  if (i > 1)
    ans->left = constructFromPrePost(preorder + 1, i - 1, postorder, i - 1);
  ans->right = constructFromPrePost(
      preorder + i, preorderSize - i,
      postorder + postorderSize - (preorderSize - i) - 1, preorderSize - i);
  return ans;
}

int main() {
  int pre1[] = {1, 2, 4, 5, 3, 6, 7}, post1[] = {4, 5, 2, 6, 7, 3, 1};
  int pre2[] = {1}, post2[] = {1};
  struct TreeNode *cfpp1 =
      constructFromPrePost(pre1, ARRAY_SIZE(pre1), post1, ARRAY_SIZE(post1));
  struct TreeNode *cfpp2 =
      constructFromPrePost(pre2, ARRAY_SIZE(pre2), post2, ARRAY_SIZE(post2));
  treenode_print(cfpp1); // expect: 1 2 3 4 5 6 7
  printf("\n");
  treenode_print(cfpp2); // expect: 1
  printf("\n");
  treenode_free(cfpp1);
  treenode_free(cfpp2);
}