Comment on page
889.Construct-Binary-Tree-from-Preorder-and-Postorder-Traversal
Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre and post are distinct positive integers.
Example 1:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Note:
1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.
Time: O(N^2) && Space: O(N^2)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
int N = pre.length;
if (N == 0) return null;
TreeNode root = new TreeNode(pre[0]);
if (N == 1) return root;
int L = 0;
for (int i = 0; i < N; i++) {
if (post[i] == pre[1])
L = i + 1;
}
root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, L+1),
Arrays.copyOfRange(post, 0, L));
root.right = constructFromPrePost(Arrays.copyOfRange(pre, L+1, N),
Arrays.copyOfRange(post, L, N-1));
return root;
}
}
Create a node
TreeNode(pre[preIndex]) as the root.Becasue root node will be lastly iterated in post order,
if root.val == post[posIndex], it means we have constructed the whole tree,If we haven't completed constructed the whole tree, So we recursively
constructFromPrePost for left sub tree and right sub tree.And finally, we'll reach the
posIndex that root.val == post[posIndex]. We increment posIndex and return our root node.class Solution {
int preIndex = 0;
int postIndex = 0;
public TreeNode constructFromPrePost(int[] pre, int[] post) {
TreeNode root = new TreeNode(pre[preIndex++]);
if (root.val != post[postIndex])
root.left = constructFromPrePost(pre, post);
if (root.val != post[postIndex])
root.right = constructFromPrePost(pre, post);
postIndex++;
return root;
}
}
O(N)
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
Deque<TreeNode> s = new ArrayDeque<>();
s.offer(new TreeNode(pre[0]));
for (int i = 1, j = 0; i < pre.length; i++) {
TreeNode node = new TreeNode(pre[i]);
while (s.getLast().val == post[j]) {
s.pollLast();
j++;
}
if (s.getLast().left == null) {
s.getLast().left = node;
} else {
s.getLast().right = node;
}
s.offer(node);
}
return s.getFirst();
}
}
Last modified 2yr ago