Description
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length3000 <= inorder[i], postorder[i] <= 3000-
inorderandpostorderconsist of unique values. - Each value of
postorderalso appears ininorder. -
inorderis guaranteed to be the inorder traversal of the tree. -
postorderis guaranteed to be the postorder traversal of the tree.
Solutions
Solution 1
Intuition
Code
class Solution {
// inorder 9,3,15,20,7
// postorder 9,15,7,20,3
// 1. get 3 from postorder
// 2. find 3 in inorder, and then split inorder to two parts
// 3. recursion 1, 2 in different part
public TreeNode buildTree(int[] inorder, int[] postorder) {
int m = inorder.length, n = postorder.length;
if (m != n) {
return null;
}
Stack<Integer> stack = new Stack<>();
for (int val : postorder) {
stack.push(val);
}
TreeNode root = helper(0, n - 1, stack, inorder);
return root;
}
private TreeNode helper(
int start, int end, Stack<Integer> stack, int[] inorder) {
if (start > end || stack.isEmpty()) {
return null;
}
TreeNode node = new TreeNode(stack.pop());
// find root in inorder
int index = start;
for (int i = start; i <= end; i++) {
if (inorder[i] == node.val) {
index = i;
break;
}
}
node.right = helper(index + 1, end, stack, inorder);
node.left = helper(start, index - 1, stack, inorder);
return node;
}
}
Complexity
- Time: O(nlogn)
- Space: O(n)
Solution 2
Intuition
Code
Complexity
- Time:
- Space:
Top comments (0)