FilesExpand file tree

 master

/

654_Maximum_Binary_Tree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

39 lines (39 loc) · 1.29 KB

 master

/

654_Maximum_Binary_Tree.java

Copy path

Top

File metadata and controls

• Code
• Blame

39 lines (39 loc) · 1.29 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

public class Solution {

public TreeNode constructMaximumBinaryTree(int[] nums) {

return construct(nums, 0, nums.length);

}

public TreeNode construct(int[] nums, int l, int r) {

if (l == r)

return null;

int max_i = max(nums, l, r);

TreeNode root = new TreeNode(nums[max_i]);

root.left = construct(nums, l, max_i);

root.right = construct(nums, max_i + 1, r);

return root;

}

public int max(int[] nums, int l, int r) {

int max_i = l;

for (int i = l; i < r; i++) {

if (nums[max_i] < nums[i])

max_i = i;

}

return max_i;

}

/*public TreeNode constructMaximumBinaryTree(int[] nums) {

// https://leetcode.com/problems/maximum-binary-tree/discuss/106146/C++-O(N)-solution

Stack<TreeNode> stack = new Stack<>();

for (int i=0; i<nums.length(); i++) {

TreeNode curr = new TreeNode(nums[i]);

while (!stack.empty() && stack.peek().val < nums[i]) {

curr.left = stack.pop();

}

if (!stack.empty())

stack.peek().right = curr;

stack.push(curr);

}

while (stack.size() != 1) {

stack.pop()

}

return stack.peek();

}*/

}