题目
Given preorder and inorder traversal of a tree, construct the binary tree.
答案
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
}
public TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
if(pl > pr) return null;
// First, take preorder[pl] as root
TreeNode root = new TreeNode(preorder[pl]);
// Second, find root in array inorder
int root_idx = il;
for(int i = il; i <= ir; i++) {
if(inorder[i] == root.val) root_idx = i;
}
int left_size = root_idx - il;
int right_size = ir - root_idx;
// Third, build subrees
root.left = build(preorder, inorder, pl + 1, pl + left_size, il, root_idx - 1);
root.right = build(preorder, inorder, pl + left_size + 1, pl + left_size + right_size, root_idx + 1, ir);
return root;
}
}
