2021/05/04
使用 SubList (31ms)
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
List<Integer> pre = Arrays.stream(preorder).boxed().collect(Collectors.toList());
List<Integer> in = Arrays.stream(inorder).boxed().collect(Collectors.toList());
return buildTree(pre, in);
}
public TreeNode buildTree(List<Integer> preorder, List<Integer> inorder) {
if (preorder.size() == 0) return null;
int rootVal = preorder.get(0);
int p = inorder.indexOf(rootVal);
List<Integer> leftInorder = inorder.subList(0, p);
List<Integer> rightInorder = inorder.subList(p + 1, inorder.size());
List<Integer> leftPreorder = preorder.subList(1, p + 1);
List<Integer> rightPreorder = preorder.subList(p + 1, preorder.size());
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}
使用 Array (8ms)
class Solution {
int indexOf(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
int rootVal = preorder[0];
int p = indexOf(inorder, rootVal);
int[] leftInorder = Arrays.copyOfRange(inorder, 0, p);
int[] rightInorder = Arrays.copyOfRange(inorder, p + 1, inorder.length);
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, p + 1);
int[] rightPreorder = Arrays.copyOfRange(preorder, p + 1, preorder.length);
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}