aboutsummaryrefslogtreecommitdiff
path: root/construct_bt_pre_post_trav.c
diff options
context:
space:
mode:
Diffstat (limited to 'construct_bt_pre_post_trav.c')
-rw-r--r--construct_bt_pre_post_trav.c42
1 files changed, 42 insertions, 0 deletions
diff --git a/construct_bt_pre_post_trav.c b/construct_bt_pre_post_trav.c
new file mode 100644
index 0000000..63eb9a9
--- /dev/null
+++ b/construct_bt_pre_post_trav.c
@@ -0,0 +1,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);
+}