var constructMaximumBinaryTree = function(nums) { // slice 实现
const n = nums.length
if (n === 0) return null
let maxNum = -1, maxIndex = 0
for (let i = 0; i < n; i++) {
if (nums[i] > maxNum) {
maxNum = nums[i]
maxIndex = i
}
}
return new TreeNode(maxNum, constructMaximumBinaryTree(nums.slice(0, maxIndex)), constructMaximumBinaryTree(nums.slice(maxIndex + 1)))
};
var constructMaximumBinaryTree = function(nums) { // 指针实现
const d = (start, end) => {
if (start === end) return null
let maxNum = -1, maxIndex = -1
for (let i = start; i < end; i++) {
if (maxNum < nums[i]) {
maxNum = nums[i]
maxIndex = i
}
}
return new TreeNode(maxNum, d(start, maxIndex), d(maxIndex + 1, end))
}
return d(0, nums.length)
};
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
const d = (start: number, end: number): TreeNode | null => {
if (start === end) return null
let maxNum = -1, maxIndex = -1
for (let i = start; i < end; i++) {
if (maxNum < nums[i]) {
maxNum = nums[i]
maxIndex = i
}
}
return new TreeNode(maxNum, d(start, maxIndex), d(maxIndex + 1, end))
}
return d(0, nums.length)
};
class Solution {
private function d(&$nums, $start, $end) {
if ($start === $end) return null;
$maxNum = -1;
$maxIndex = -1;
for ($i = $start; $i < $end; $i++) {
if ($maxNum < $nums[$i]) {
$maxNum = $nums[$i];
$maxIndex = $i;
}
}
return new TreeNode($maxNum, $this->d($nums, $start, $maxIndex), $this->d($nums, $maxIndex + 1, $end));
}
function constructMaximumBinaryTree($nums) {
return $this->d($nums, 0, count($nums));
}
}
func constructMaximumBinaryTree(nums []int) *TreeNode {
var d func(start int, end int) *TreeNode
d = func(start int, end int) *TreeNode {
if start == end {
return nil
}
maxNum, maxIndex := -1, 0
for i := start; i < end; i++ {
if maxNum < nums[i] {
maxNum = nums[i]
maxIndex = i
}
}
return &TreeNode{maxNum, d(start, maxIndex), d(maxIndex + 1, end)}
}
return d(0, len(nums))
}
class Solution {
private int[] nums;
private TreeNode d(int start, int end) {
if (start == end) return null;
int maxNum = -1, maxIndex = -1;
for (int i = start; i < end; i++) {
if (maxNum < nums[i]) {
maxNum = nums[i];
maxIndex = i;
}
}
return new TreeNode(maxNum, d(start, maxIndex), d(maxIndex + 1, end));
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
this.nums = nums;
return d(0, nums.length);
}
}
public class Solution {
private int[] nums;
private TreeNode d(int start, int end) {
if (start == end) return null;
int maxNum = -1, maxIndex = 0;
for (int i = start; i < end; i++) {
if (maxNum < nums[i]) {
maxNum = nums[i];
maxIndex = i;
}
}
return new TreeNode(maxNum, d(start, maxIndex), d(maxIndex + 1, end));
}
public TreeNode ConstructMaximumBinaryTree(int[] nums) {
this.nums = nums;
return d(0, nums.Length);
}
}
struct TreeNode* d(int* nums, int start, int end) {
if (start == end) return NULL;
int maxNum = -1, maxIndex = 0;
for (int i = start; i < end; i++) {
if (maxNum < nums[i]) {
maxNum = nums[i];
maxIndex = i;
}
}
struct TreeNode* obj = malloc(sizeof(struct TreeNode));
obj->val = maxNum;
obj->left = d(nums, start, maxIndex);
obj->right = d(nums, maxIndex + 1, end);
return obj;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
return d(nums, 0, numsSize);
}
class Solution {
private:
TreeNode* d(vector<int>& nums, int start, int end) {
if (start == end) return nullptr;
int maxNum = -1, maxIndex = 0;
for (int i = start; i < end; i++) {
if (maxNum < nums[i]) {
maxNum = nums[i];
maxIndex = i;
}
}
return new TreeNode(maxNum, d(nums, start, maxIndex), d(nums, maxIndex + 1, end));
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return d(nums, 0, nums.size());
}
};
class Solution:
def d(self, start: int, end: int) -> Optional[TreeNode]:
if start == end: return None
maxNum, maxIndex = -1, 0
for i in range(start, end):
if maxNum < self.nums[i]:
maxNum = self.nums[i]
maxIndex = i
return TreeNode(maxNum, self.d(start, maxIndex), self.d(maxIndex + 1, end))
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
self.nums = nums
return self.d(0, len(nums))
单调栈 · 递减
var constructMaximumBinaryTree = function(nums) {
const stack = [], n = nums.length, trees = new Array(n)
for (let i = 0; i < n; i++) {
trees[i] = new TreeNode(nums[i])
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
trees[i].left = trees[stack.pop()]
}
if (stack.length) {
trees[stack[stack.length - 1]].right = trees[i]
}
stack.push(i)
}
return trees[stack[0]]
};
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
const n = nums.length, stack = [], trees = new Array(n)
for (let i = 0; i < n; i++) {
trees[i] = new TreeNode(nums[i])
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
trees[i].left = trees[stack.pop()]
}
if (stack.length) trees[stack[stack.length - 1]].right = trees[i]
stack.push(i)
}
return trees[stack[0]]
};
class Solution {
function constructMaximumBinaryTree($nums) {
$n = count($nums);
$stack = [];
$trees = array_fill(0, $n, null);
for ($i = 0; $i < $n; $i++) {
$trees[$i] = new TreeNode($nums[$i]);
while (count($stack) && $nums[$i] > $nums[$stack[count($stack) - 1]]) {
$trees[$i]->left = $trees[array_pop($stack)];
}
if (count($stack)) {
$trees[$stack[count($stack) - 1]]->right = $trees[$i];
}
$stack []= $i;
}
return $trees[$stack[0]];
}
}
func constructMaximumBinaryTree(nums []int) *TreeNode {
n, stack := len(nums), []int{}
trees := make([]*TreeNode, n)
for i := 0; i < n; i++ {
trees[i] = &TreeNode{nums[i], nil, nil}
for len(stack) > 0 && nums[i] > nums[stack[len(stack) - 1]] {
trees[i].Left = trees[stack[len(stack) - 1]]
stack = stack[:len(stack) - 1]
}
if len(stack) > 0 {
trees[stack[len(stack) - 1]].Right = trees[i]
}
stack = append(stack, i)
}
return trees[stack[0]]
}
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
int n = nums.length;
TreeNode[] trees = new TreeNode[n];
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; i++) {
trees[i] = new TreeNode(nums[i], null, null);
while (stack.isEmpty() == false && nums[i] > nums[stack.peek()]) {
trees[i].left = trees[stack.pop()];
}
if (stack.isEmpty() == false) {
trees[stack.peek()].right = trees[i];
}
stack.push(i);
}
return trees[stack.getLast()];
}
}
public class Solution {
public TreeNode ConstructMaximumBinaryTree(int[] nums) {
int n = nums.Length;
Stack<int> st = new Stack<int>();
TreeNode[] trees = new TreeNode[n];
for (int i = 0; i < n; i++) {
trees[i] = new TreeNode(nums[i]);
while (st.Count > 0 && nums[i] > nums[st.Peek()]) {
trees[i].left = trees[st.Pop()];
}
if (st.Count > 0) {
trees[st.Peek()].right = trees[i];
}
st.Push(i);
}
int[] a = st.ToArray();
return trees[a[a.Length - 1]];
}
}
class Solution { // stack 实现
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int n = nums.size();
stack<int> st;
vector<TreeNode*> trees(n);
for (int i = 0; i < n; i++) {
trees[i] = new TreeNode(nums[i]);
while (st.empty() == false && nums[i] > nums[st.top()]) {
trees[i]->left = trees[st.top()];
st.pop();
}
if (st.empty() == false) {
trees[st.top()]->right = trees[i];
}
st.push(i);
}
while (st.size() > 1) st.pop();
return trees[st.top()];
}
};
class Solution { // vector 实现
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int n = nums.size();
vector<int> st;
vector<TreeNode*> trees(n);
for (int i = 0; i < n; i++) {
trees[i] = new TreeNode(nums[i]);
while (st.empty() == false && nums[i] > nums[st.back()]) {
trees[i]->left = trees[st.back()];
st.pop_back();
}
if (st.empty() == false) {
trees[st.back()]->right = trees[i];
}
st.push_back(i);
}
return trees[st.front()];
}
};
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
n, stack = len(nums), []
trees = [None] * n
for i in range(n):
trees[i] = TreeNode(nums[i])
while len(stack) > 0 and nums[i] > nums[stack[-1]]:
trees[i].left = trees[stack.pop()]
if len(stack) > 0:
trees[stack[-1]].right = trees[i]
stack.append(i)
return trees[stack[0]]
