aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--construct_bt_pre_post_trav.c42
-rw-r--r--construct_bt_pre_post_trav.py41
2 files changed, 83 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);
+}
diff --git a/construct_bt_pre_post_trav.py b/construct_bt_pre_post_trav.py
new file mode 100644
index 0000000..ec24e6d
--- /dev/null
+++ b/construct_bt_pre_post_trav.py
@@ -0,0 +1,41 @@
+# 889. Construct Binary Tree from Preorder and Postorder Traversal
+from leetcode import TreeNode
+
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def constructFromPrePost(self, preorder, postorder):
+ """
+ :type preorder: List[int]
+ :type postorder: List[int]
+ :rtype: Optional[TreeNode]
+ """
+ stack, j = [TreeNode(preorder[0])], 0
+ for i in preorder[1:]:
+ node = TreeNode(i)
+ while stack[-1].val == postorder[j]:
+ stack.pop()
+ j += 1
+ if not stack[-1].left:
+ stack[-1].left = node
+ else:
+ stack[-1].right = node
+ stack.append(node)
+ return stack[0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.constructFromPrePost(
+ preorder=[1, 2, 4, 5, 3, 6, 7], postorder=[4, 5, 2, 6, 7, 3, 1]
+ )
+ )
+ print(obj.constructFromPrePost(preorder=[1], postorder=[1]))