Description
Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
If there exist multiple answers, you can return any of them.
Example 1:
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Example 2:
Input: preorder = [1], postorder = [1]
Output: [1]
Constraints:
1 <= preorder.length <= 301 <= preorder[i] <= preorder.length- All the values of
preorder are unique.
postorder.length == preorder.length1 <= postorder[i] <= postorder.length- All the values of
postorder are unique.
- It is guaranteed that
preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.
Solutions
Solution 1: Recursion
The order of pre-order traversal is: root node -> left subtree -> right subtree, and the order of post-order traversal is: left subtree -> right subtree -> root node.
Therefore, the root node of the binary tree must be the first node of the pre-order traversal and the last node of the post-order traversal.
Next, we need to determine the range of the left and right subtrees of the binary tree.
If the binary tree has a left subtree, then the root node of the left subtree must be the second node of the pre-order traversal; if the binary tree does not have a left subtree, then the second node of the pre-order traversal must be the root node of the right subtree. Since the results of post-order traversal in these two cases are the same, we can take the second node of the pre-order traversal as the root node of the left subtree, and then find its position in the post-order traversal, so as to determine the range of the left subtree.
Specifically, we design a recursive function dfs(a, b, c, d), where [a, b] represents the range of pre-order traversal, and [c, d] represents the range of post-order traversal. The function of this function is to construct the root node of the binary tree based on the pre-order traversal [a, b] and the post-order traversal [c, d]. The answer is dfs(0, n - 1, 0, n - 1), where n is the length of the pre-order traversal.
The execution steps of the function dfs(a, b, c, d) are as follows:
- If a > b, the range is empty, return a null node directly.
- Otherwise, we construct a new node root, its value is the value of the first node in the pre-order traversal, which is preorder[a].
- If a equals b, it means that root has neither a left subtree nor a right subtree, return root directly.
- Otherwise, the value of the root node of the left subtree is preorder[a + 1], we find the position of preorder[a + 1] in the post-order traversal, denoted as i. The number of nodes in the left subtree m = i - c + 1, from this we know that the range of the left subtree in the pre-order traversal is [a + 1, a + m], the range in the post-order traversal is [c, i], the range of the right subtree in the pre-order traversal is [a + m + 1, b], and the range in the post-order traversal is [i + 1, d - 1].
- Knowing the range of the left and right subtrees, we can recursively rebuild the left and right subtrees, and then make the root nodes of the left and right subtrees as the left and right child nodes of root respectively. Finally return root.
In the function dfs(a, b, c, d), we need to use a hash table pos, which stores the position of each node in the post-order traversal. At the beginning of the function, we can calculate this hash table first, so that we can find the position of any node in the post-order traversal in O(1) time.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
PythonJavaC++GoTypeScript
# 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]
) -> Optional[TreeNode]:
def dfs(a: int, b: int, c: int, d: int) -> Optional[TreeNode]:
if a > b:
return None
root = TreeNode(preorder[a])
if a == b:
return root
i = pos[preorder[a + 1]]
m = i - c + 1
root.left = dfs(a + 1, a + m, c, i)
root.right = dfs(a + m + 1, b, i + 1, d - 1)
return root
pos = {x: i for i, x in enumerate(postorder)}
return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)(code-box)
/**
* 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 {
private Map<Integer, Integer> pos = new HashMap<>();
private int[] preorder;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
this.preorder = preorder;
for (int i = 0; i < postorder.length; ++i) {
pos.put(postorder[i], i);
}
return dfs(0, preorder.length - 1, 0, postorder.length - 1);
}
private TreeNode dfs(int a, int b, int c, int d) {
if (a > b) {
return null;
}
TreeNode root = new TreeNode(preorder[a]);
if (a == b) {
return root;
}
int i = pos.get(preorder[a + 1]);
int m = i - c + 1;
root.left = dfs(a + 1, a + m, c, i);
root.right = dfs(a + m + 1, b, i + 1, d - 1);
return root;
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
unordered_map<int, int> pos;
int n = postorder.size();
for (int i = 0; i < n; ++i) {
pos[postorder[i]] = i;
}
function<TreeNode*(int, int, int, int)> dfs = [&](int a, int b, int c, int d) -> TreeNode* {
if (a > b) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[a]);
if (a == b) {
return root;
}
int i = pos[preorder[a + 1]];
int m = i - c + 1;
root->left = dfs(a + 1, a + m, c, i);
root->right = dfs(a + m + 1, b, i + 1, d - 1);
return root;
};
return dfs(0, n - 1, 0, n - 1);
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
pos := map[int]int{}
for i, x := range postorder {
pos[x] = i
}
var dfs func(int, int, int, int) *TreeNode
dfs = func(a, b, c, d int) *TreeNode {
if a > b {
return nil
}
root := &TreeNode{Val: preorder[a]}
if a == b {
return root
}
i := pos[preorder[a+1]]
m := i - c + 1
root.Left = dfs(a+1, a+m, c, i)
root.Right = dfs(a+m+1, b, i+1, d-1)
return root
}
return dfs(0, len(preorder)-1, 0, len(postorder)-1)
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
const pos: Map<number, number> = new Map();
const n = postorder.length;
for (let i = 0; i < n; ++i) {
pos.set(postorder[i], i);
}
const dfs = (a: number, b: number, c: number, d: number): TreeNode | null => {
if (a > b) {
return null;
}
const root = new TreeNode(preorder[a]);
if (a === b) {
return root;
}
const i = pos.get(preorder[a + 1])!;
const m = i - c + 1;
root.left = dfs(a + 1, a + m, c, i);
root.right = dfs(a + m + 1, b, i + 1, d - 1);
return root;
};
return dfs(0, n - 1, 0, n - 1);
}(code-box)
Solution 2: Another Recursive Approach
We can design a recursive function dfs(i, j, n), where i and j represent the starting points of the pre-order and post-order traversals, respectively, and n represents the number of nodes. This function constructs the root node of the binary tree based on the pre-order traversal [i, i + n - 1] and post-order traversal [j, j + n - 1]. The answer is dfs(0, 0, n), where n is the length of the pre-order traversal.
The execution steps of the function dfs(i, j, n) are as follows:
- If n = 0, the range is empty, so return a null node directly.
- Otherwise, we construct a new node root, whose value is the value of the first node in the pre-order traversal, which is preorder[i].
- If n = 1, it means that root has neither a left subtree nor a right subtree, so return root directly.
- Otherwise, the value of the root node of the left subtree is preorder[i + 1]. We find the position of preorder[i + 1] in the post-order traversal, denoted as k. Then the number of nodes in the left subtree is m = k - j + 1, and the number of nodes in the right subtree is n - m - 1. We recursively rebuild the left and right subtrees, and then make the root nodes of the left and right subtrees the left and right child nodes of root, respectively. Finally, return root.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
PythonJavaC++GoTypeScript
# 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]
) -> Optional[TreeNode]:
def dfs(i: int, j: int, n: int) -> Optional[TreeNode]:
if n <= 0:
return None
root = TreeNode(preorder[i])
if n == 1:
return root
k = pos[preorder[i + 1]]
m = k - j + 1
root.left = dfs(i + 1, j, m)
root.right = dfs(i + m + 1, k + 1, n - m - 1)
return root
pos = {x: i for i, x in enumerate(postorder)}
return dfs(0, 0, len(preorder))(code-box)
/**
* 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 {
private Map<Integer, Integer> pos = new HashMap<>();
private int[] preorder;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
this.preorder = preorder;
for (int i = 0; i < postorder.length; ++i) {
pos.put(postorder[i], i);
}
return dfs(0, 0, preorder.length);
}
private TreeNode dfs(int i, int j, int n) {
if (n <= 0) {
return null;
}
TreeNode root = new TreeNode(preorder[i]);
if (n == 1) {
return root;
}
int k = pos.get(preorder[i + 1]);
int m = k - j + 1;
root.left = dfs(i + 1, j, m);
root.right = dfs(i + m + 1, k + 1, n - m - 1);
return root;
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
unordered_map<int, int> pos;
int n = postorder.size();
for (int i = 0; i < n; ++i) {
pos[postorder[i]] = i;
}
function<TreeNode*(int, int, int)> dfs = [&](int i, int j, int n) -> TreeNode* {
if (n <= 0) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[i]);
if (n == 1) {
return root;
}
int k = pos[preorder[i + 1]];
int m = k - j + 1;
root->left = dfs(i + 1, j, m);
root->right = dfs(i + m + 1, k + 1, n - m - 1);
return root;
};
return dfs(0, 0, n);
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
pos := map[int]int{}
for i, x := range postorder {
pos[x] = i
}
var dfs func(int, int, int) *TreeNode
dfs = func(i, j, n int) *TreeNode {
if n <= 0 {
return nil
}
root := &TreeNode{Val: preorder[i]}
if n == 1 {
return root
}
k := pos[preorder[i+1]]
m := k - j + 1
root.Left = dfs(i+1, j, m)
root.Right = dfs(i+m+1, k+1, n-m-1)
return root
}
return dfs(0, 0, len(preorder))
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
const pos: Map<number, number> = new Map();
const n = postorder.length;
for (let i = 0; i < n; ++i) {
pos.set(postorder[i], i);
}
const dfs = (i: number, j: number, n: number): TreeNode | null => {
if (n <= 0) {
return null;
}
const root = new TreeNode(preorder[i]);
if (n === 1) {
return root;
}
const k = pos.get(preorder[i + 1])!;
const m = k - j + 1;
root.left = dfs(i + 1, j, m);
root.right = dfs(i + 1 + m, k + 1, n - 1 - m);
return root;
};
return dfs(0, 0, n);
}(code-box)
