0105. Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
Description
Given two integer arrays preorder
and inorder
where preorder
is the preorder traversal of a binary tree and inorder
is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:

**Input:** preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
**Output:** [3,9,20,null,null,15,7]
Example 2:
**Input:** preorder = [-1], inorder = [-1]
**Output:** [-1]
Constraints:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
andinorder
consist of unique values.Each value of
inorder
also appears inpreorder
.preorder
is guaranteed to be the preorder traversal of the tree.inorder
is guaranteed to be the inorder traversal of the tree.
ac
// Tree intuition, divide & conquer recursion
// find root index in in-order is the key: if (preorder[pstart] == inorder[i]) rootIdx = i;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// pre-order 1st -> find mid int in-order
// divide left / right parts, recursion
// edge cases
if (preorder.length == 0 || inorder.length == 0) return null;
return helper(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}
private TreeNode helper(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend) {
// exit
if (pstart > pend || istart > iend) return null;
if (pstart == pend || istart == iend) return new TreeNode(preorder[pstart]);
// recursion
// find root index
int rootIdx = -1;
for (int i = istart; i <= iend; i++) {
if (preorder[pstart] == inorder[i]){
rootIdx = i;
break;
}
}
int len = rootIdx - istart;
// divdide
TreeNode root = new TreeNode(inorder[rootIdx]);
root.left = helper(preorder, pstart+1, pstart+len, inorder, istart, rootIdx-1);
root.right = helper(preorder, pstart+len+1, pend, inorder, rootIdx+1, iend);
return root;
}
}
Previous0104. Maximum Depth of Binary TreeNext0106. Construct Binary Tree from Inorder and Postorder Traversal
Last updated
Was this helpful?