Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/889.html

889. Construct Binary Tree from Preorder and Postorder Traversal

Level

Medium

Description

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.

Solution

The preorder traversal visits the binary tree in such an order: root, left subtree, and right subtree. For each subtree, the nodes are also visited in the order of preorder traversal.

The postorder traversal visits the binary tree in such an order: left subtree, right subtree, and root. For each subtree, the nodes are also visited in the order of postorder traversal.

This problem can be solved using recursion. Base cases are when the number of nodes is 0 or 1. If the number of nodes is 0, then return null. If the number of nodes is 1, then create the root using the value of the node, and return the root.

If the number of nodes is greater than 1, suppose the left child always exist. The element pre[1] is the value of the left child of the root. Find the value pre[1] in post, which is the last node to be visited in the left subtree in postorder traversal, and the number of nodes in the left subtree can be obtained. The number of nodes in the right subtree can be obtained as well. Then use the subarrays of pre and post to create the left subtree and the right subtree respectively. Finally, return the root.

  • public class Construct_Binary_Tree_from_Preorder_and_Postorder_Traversal {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    class Solution {

        /*
            preorder -> [1] [2,4,5] [3,6,7]
            postorder -> [4,5,2] [6,7,3] [root]
         */
        public TreeNode constructFromPrePost(int[] pre, int[] post) {

            return helper(pre, 0, pre.length - 1, post, 0, post.length - 1);
        }

        // preL 和 preR 分别表示左子树区间的开头和结尾位置
        // postL 和 postR 表示右子树区间的开头和结尾位置
        TreeNode helper(int[] pre, int preL, int preR, int[] post, int postL, int postR) {
            if (preL > preR || postL > postR) {
                return null;
            }

            // root node
            TreeNode node = new TreeNode(pre[preL]);

            if (preL == preR) { // leaf node
                return node;
            }

            // 找左子树的根结点(pre[preL + 1)  在 post[] 中的位置
            // pre[preL + 1 here "+1" to skip above root node
            int idx = -1;
            for (idx = postL; idx <= postR; ++idx) {
                if (pre[preL + 1] == post[idx]) {
                    break;
                }
            }

            // left sub tree length: (idx - postL)
            // right sub tree length:
            node.left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
            node.right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1); // postR - 1 to skip root

            return node;
        }
    }
}

############

class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        int length = pre.length;
        if (length == 0)
            return null;
        else if (length == 1)
            return new TreeNode(pre[0]);
        else {
            TreeNode root = new TreeNode(pre[0]);
            int leftChild = pre[1];
            int leftCount = 0;
            for (int i = 0; i < length; i++) {
                if (post[i] == leftChild) {
                    leftCount = i + 1;
                    break;
                }
            }
            root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, 1 + leftCount), Arrays.copyOfRange(post, 0, leftCount));
            root.right = constructFromPrePost(Arrays.copyOfRange(pre, 1 + leftCount, length), Arrays.copyOfRange(post, leftCount, length - 1));
            return root;
        }
    }
}


  • // OJ: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
// Time: O(N^2)
// Space: O(N)
class Solution {
private:
    TreeNode *construct(vector<int> &pre, int preBegin, int preEnd,
                       vector<int> &post, int postBegin, int postEnd) {
        if (preBegin >= preEnd) return NULL;
        auto node = new TreeNode(pre[preBegin]);
        if (preBegin + 1 < preEnd) {
            int leftVal = pre[preBegin + 1];
            int postMid = find(post.begin() + postBegin, post.begin() + postEnd - 1, leftVal) - post.begin();
            int postLeftLength = postMid - postBegin + 1;
            node->left = construct(pre, preBegin + 1, preBegin + 1 + postLeftLength,
                                   post, postBegin, postMid + 1);
            node->right = construct(pre, preBegin + 1 + postLeftLength, preEnd,
                                   post, postMid + 1, postEnd - 1);
        }
        return node;
    }
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return construct(pre, 0, pre.size(), post, 0, post.size());
    }
};

  • # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
>>> a = [1,2,3,4,5]
>>> a[0:2]
[1, 2]

so right index is exclusive
'''

class Solution(object):
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        if not pre or not post: return None
        root = TreeNode(pre[0])
        if len(pre) == 1:
            return root
        idx = pre.index(post[-2])
        root.left = self.constructFromPrePost(pre[1:idx], post[:idx-1])
        root.right = self.constructFromPrePost(pre[idx:], post[idx-1:-1])
        return root

############

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(
        self, preorder: List[int], postorder: List[int]
    ) -> TreeNode:
        n = len(preorder)
        if n == 0:
            return None
        root = TreeNode(preorder[0])
        if n == 1:
            return root
        for i in range(n - 1):
            if postorder[i] == preorder[1]:
                root.left = self.constructFromPrePost(
                    preorder[1 : 1 + i + 1], postorder[: i + 1]
                )
                root.right = self.constructFromPrePost(
                    preorder[1 + i + 1 :], postorder[i + 1 : -1]
                )
                return root


  • /**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	postMap := make(map[int]int)
	for index, v := range postorder {
		postMap[v] = index
	}
	var dfs func(prel, prer, postl, postr int) *TreeNode
	dfs = func(prel, prer, postl, postr int) *TreeNode {
		if prel > prer {
			return nil
		}
		root := &TreeNode{Val: preorder[prel]}
		if prel == prer {
			return root
		}
		leftRootIndex := postMap[preorder[prel+1]]
		leftLength := leftRootIndex - postl + 1
		root.Left = dfs(prel+1, prel+leftLength, postl, leftRootIndex)
		root.Right = dfs(prel+leftLength+1, prer, leftRootIndex+1, postr-1)
		return root
	}
	return dfs(0, len(preorder)-1, 0, len(postorder)-1)
}

All Problems

All Solutions