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[]
andpost[]
are both permutations of1, 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.
Java
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;
}
}
}
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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;
}
}
}