題目
Given inorder and postorder traversal of a tree, construct the binary tree.
答案
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, postorder, 0, postorder.length - 1, 0, inorder.length - 1);
}
public TreeNode build(int[] inorder, int[] postorder, int pl, int pr, int il, int ir) {
if(pl > pr) return null;
// First, take postorder[pr] as root
TreeNode root = new TreeNode(postorder[pr]);
// 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(inorder, postorder, pr - right_size - left_size, pr - right_size - 1, il, root_idx - 1);
root.right = build(inorder, postorder, pr - right_size, pr - 1, root_idx + 1, ir);
return root;
}
}
