構(gòu)建一顆「最大樹(shù)」。
注意consruct的時(shí)候最后的return root; 我參考了serialize and deserialize binary tree的build tree 的過(guò)程软舌。
這周contest的第二題车柠，一次AC了還挺開(kāi)心的攘须，而且用的時(shí)間不長(zhǎng)。我發(fā)現(xiàn)當(dāng)你沒(méi)思路的時(shí)候或是思維陷入死循環(huán)jiang化的時(shí)候時(shí)間過(guò)得特別快，有思路就不一樣。
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;
}
