FilesExpand file tree

 master

/

MaximumBinaryTree654.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

117 lines (103 loc) · 3.28 KB

 master

/

MaximumBinaryTree654.java

Copy path

Top

File metadata and controls

• Code
• Blame

117 lines (103 loc) · 3.28 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

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

/**

* Given an integer array with no duplicates. A maximum tree building on this

* array is defined as follow:

*

* The root is the maximum number in the array.

* The left subtree is the maximum tree constructed from left part subarray

* divided by the maximum number.

* The right subtree is the maximum tree constructed from right part subarray

* divided by the maximum number.

*

* Construct the maximum tree by the given array and output the root node of

* this tree.

*

* Example 1:

* Input: [3,2,1,6,0,5]

* Output: return the tree root node representing the following tree:

*

* 6

* / \

* 3 5

* \ /

* 2 0

* \

* 1

* Note:

* The size of the given array will be in the range [1,1000].

*/

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class MaximumBinaryTree654 {

public TreeNode constructMaximumBinaryTree(int[] nums) {

return constructMaximumBinaryTree(nums, 0, nums.length-1);

}

public TreeNode constructMaximumBinaryTree(int[] nums, int lo, int hi) {

if (lo > hi) return null;

if (lo == hi) return new TreeNode(nums[lo]);

int idx = maxIndex(nums, lo, hi);

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

root.left = constructMaximumBinaryTree(nums, lo, idx-1);

root.right = constructMaximumBinaryTree(nums, idx+1, hi);

return root;

}

private int maxIndex(int[] nums, int lo, int hi) {

int res = lo;

int max = nums[lo];

for (int i=lo; i<=hi; i++) {

if (nums[i] > max) {

max = nums[i];

res = i;

}

}

return res;

}

public TreeNode constructMaximumBinaryTree2(int[] nums) {

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

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

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

if (stack.isEmpty() || stack.peek().val > nums[i]) {

stack.push(curr);

continue;

}

TreeNode left = null;

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

TreeNode temp = stack.pop();

temp.right = left;

left = temp;

}

curr.left = left;

stack.push(curr);

}

TreeNode res = null;

while (!stack.isEmpty()) {

TreeNode temp = stack.pop();

temp.right = res;

res = temp;

}

return res;

}

/**

* https://leetcode.com/problems/maximum-binary-tree/discuss/106156/Java-worst-case-O(N)-solution

*/

public TreeNode constructMaximumBinaryTree3(int[] nums) {

Deque<TreeNode> stack = new LinkedList<>();

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

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

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

curr.left = stack.pop();

}

if(!stack.isEmpty()) {

stack.peek().right = curr;

}

stack.push(curr);

}

return stack.isEmpty() ? null : stack.removeLast();

}

}