889. Construct Binary Tree from Preorder and Postorder Traversal
Explanation:
To construct a binary tree from preorder and postorder traversals, we need to understand the properties of these traversal orders. In a preorder traversal, the root node is visited first, then the left subtree, and finally the right subtree. In a postorder traversal, the left subtree is visited first, then the right subtree, and finally the root node.
By using these properties, we can construct the binary tree recursively. The root of the tree is the first element in the preorder traversal. We then find the index of the root in the postorder traversal. This index divides the postorder array into left and right subtrees. We recursively construct the left and right subtrees using the corresponding elements in the preorder and postorder arrays.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
return buildTree(pre, 0, pre.length - 1, post, 0, post.length - 1);
}
public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
if (preStart > preEnd || postStart > postEnd) return null;
TreeNode root = new TreeNode(pre[preStart]);
if (preStart == preEnd) return root;
int idx = postStart;
while (post[idx] != pre[preStart + 1]) idx++;
int len = idx - postStart + 1;
root.left = buildTree(pre, preStart + 1, preStart + len, post, postStart, idx);
root.right = buildTree(pre, preStart + len + 1, preEnd, post, idx + 1, postEnd - 1);
return root;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.