构建一颗「最大树」。
注意consruct的时候最后的return root; 我参考了serialize and deserialize binary tree的build tree 的过程。
这周contest的第二题,一次AC了还挺开心的,而且用的时间不长。我发现当你没思路的时候或是思维陷入死循环jiang化的时候时间过得特别快,有思路就不一样。
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length - 1);
}
private TreeNode construct(int[] nums, int i, int j) {
if (i > j) return null;
int[] arr = findMax(nums, i, j);
TreeNode root = new TreeNode(arr[0]);
root.left = construct(nums, i, arr[1] - 1);
root.right = construct(nums, arr[1] + 1, j);
return root;
}
private int[] findMax(int[] nums, int i, int j) {
int[] res = new int[2];
res[0] = Integer.MIN_VALUE;
for (int k = i; k <= j; k++) {
if (nums[k] > res[0]) {
res[0] = nums[k];
res[1] = k;
}
}
return res;
}
网友评论