889.Construct-Binary-Tree-from-Preorder-and-Postorder-Traversal

889. Construct Binary Tree from Preorder and Postorder Traversal

题目地址

https://leetcode.com/problems/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();
  }
}