Leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal

Problem Description

The task at hand requires us to construct a binary tree from the provided preorder and post-order traversals of a binary tree. Both these traversals are represented as arrays with distinct positive integer elements that stand for node values. As there may be multiple solutions for a given combination of traversals, we are allowed to return any valid answer.

For example:

1
2bash
3Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
4Output: [1,2,3,4,5,6,7]

In the above example, we can form a binary tree whose preorder traversal matches pre and whose post-order traversal matches post.

Solution Approach

The solution to this problem involves utilizing the properties of binary trees and the behavior of preorder and post-order traversals.

• In a pre-order traversal, the root node is visited first, followed by the left subtree and then the right subtree.

• In a post-order traversal, the left subtree is visited first, then the right subtree, and finally the root node.

Therefore, the first element in the pre-order traversal array will be the root node of our binary tree. The second element will be the root of the left subtree, which we can find in the post-order traversal array. The index of this value in the post-order array signals the size of the left subtree and we will use this to recursively construct the left and right subtrees.

The problem is solved using the Depth-First Search (DFS) algorithm with a recursive approach.

Python Solution

1
2python
3class Solution:
4    def constructFromPrePost(self, pre, post):
5        if not pre:
6            return None
7        root = TreeNode(pre[0])
8        if len(pre) == 1:
9            return root
10        
11        L = post.index(pre[1]) + 1
12        root.left = self.constructFromPrePost(pre[1:L+1], post[0:L])
13        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])
14        return root

In the Python solution, we create the root node and then find the subarray that represents the left subtree. We then recursively call the function to construct the left and right subtrees.

Java Solution

1
2java
3class Solution {
4  public TreeNode constructFromPrePost(int[] pre, int[] post) {
5    int N = pre.length;
6    if (N == 0) return null;
7    TreeNode root = new TreeNode(pre[0]);
8    if (N == 1) return root;
9
10    int L = 0;
11    for (int i = 0; i < N; i++) {
12        if (post[i] == pre[1]){
13            L = i + 1;
14            break;
15        }
16    }
17
18    root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, L + 1), 
19      Arrays.copyOfRange(post, 0, L));
20    root.right = constructFromPrePost(Arrays.copyOfRange(pre, L + 1, N), 
21      Arrays.copyOfRange(post, L, N - 1));
22    return root;
23  }
24}

In the Java solution, we use the Arrays.copyOfRange() function to extract the relevant subarrays.

JavaScript Solution

1
2java
3const constructFromPrePost = function(pre, post) {
4        if (!pre.length) return null;
5        let root= new TreeNode(pre[0]),
6             idx = post.indexOf(pre[1]);
7        root.left = constructFromPrePost(pre.slice(1, idx + 2), post.slice(0, idx + 1));
8        root.right = constructFromPrePost(pre.slice(idx + 2), post.slice(idx + 1, -1));
9        return root;
10};

In the Javascript solution, we use the slice() function to get the part of the array that represents the left or the right subtree.

C# Solution

1
2csharp
3public class Solution {
4    public TreeNode ConstructFromPrePost(int[] pre, int[] post) {
5        if (pre.Length == 0)
6            return null;
7        TreeNode root = new TreeNode(pre[0]);
8        if (pre.Length == 1)
9            return root;
10
11        int L = Array.FindIndex(post, x => x == pre[1]) + 1;
12        
13        root.left = ConstructFromPrePost(pre.Skip(1).Take(L).ToArray(), 
14          post.Take(L).ToArray());
15        root.right = ConstructFromPrePost(pre.Skip(L + 1).ToArray(), 
16          post.Skip(L).Take(pre.Length - L - 1).ToArray());
17        return root;
18    }
19}

In the C# solution, the Take() and Skip() functions are used to obtain the subarrays needed to build the left and right subtrees.

C++ Solution

1
2cpp
3class Solution {
4public:
5    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
6        stack<TreeNode*> s;
7        TreeNode *root = new TreeNode(pre[0]);
8        s.push(root);
9        for (int i = 1, j = 0; i < pre.size(); ++i) {
10            TreeNode *node = new TreeNode(pre[i]);
11            while (s.top()->val == post[j]) {
12                s.pop();
13                ++j;
14            }
15            if (s.top()->left == nullptr) {
16                s.top()->left = node;
17            } else {
18                s.top()->right = node;
19            }
20            s.push(node);
21        }
22        return root;
23    }
24};

The C++ solution uses a stack to keep track of the unprocessed nodes. For each element in the pre-order array, a new node is created. This node is added as a left or right child of the node at the top of the stack. Nodes are popped from the stack when they match the current post-order element, indicating that the sub-tree rooted at this node has been completely built. This node is then returned as the root of the binary tree.## Go Solution

1
2go
3type TreeNode struct {
4    Val   int
5    Left  *TreeNode
6    Right *TreeNode
7}
8
9func constructFromPrePost(pre []int, post []int) *TreeNode {
10    if len(pre) == 0 {
11        return nil
12    }
13
14    root := &TreeNode{Val: pre[0]}
15    if len(pre) == 1 {
16        return root
17    }
18
19    var L int
20    for i, v := range post {
21        if v == pre[1] {
22            L = i + 1
23            break
24        }
25    }
26    root.Left = constructFromPrePost(pre[1:L+1], post[:L])
27    root.Right = constructFromPrePost(pre[L+1:], post[L:len(post)-1])
28    return root
29}

In the Go solution, we follow the same procedure as before: creating a new TreeNode for the root, finding the length of the left subtree, and then recursively calling the function on the left and right subtrees.

In summary, the main idea in this problem is to leverage the properties of preorder and postorder tree traversal sequences. Because the tree's root is always the first item in its preorder sequence and the last item in its postorder sequence, we can recursively find all subtrees' roots. Despite our solution involving subtle logic and recursion, its time and space complexity is linear, making it quite efficient. Remember that unless otherwise directed, you shouldn't assume that the given tree is binary. We assumed it here because binary tree was mentioned in the problem description, but tree problems can often be solved similarly for trees of any degree!