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.

代码

Approach #1 Recursion

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;
}
}

Approach #2

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;
}
}

Approach #3 Iterative

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();
}
}