题目描述
一个数组的MaxTree定义如下： 数组必须没有重复元素。 MaxTree是一棵二叉树， 数组的每一个值对应一个二叉树节点。 包括MaxTree树在内且在其中的每一棵子树上， 值最大的节点都是树的头。 给定一个没有重复元素的数组arr， 写出生成这个数组的MaxTree的函数， 要求如果数组长度为N， 则时间复杂度为O(N)、 额外空间复杂度为O(N)。
解题思路
解法一：可以利用堆，构造堆的时间复杂度是O(N) 解法二：利用单调栈求出数组中每个位置左右最近的比它大的值，然后让左右都为null的结点作为头结点，只有左边大的的作为左边结点的左孩子，只有右边结点大的作为右边结点的右孩子，左右比它大的都有的，选择两个中较小的，作为较小的结点的孩子
代码
package TestNode
.StackAndQueue
;
import java
.util
.HashMap
;
import java
.util
.Stack
;
public class MaxTree {
static class Node{
public int value
;
public Node left
;
public Node right
;
public Node(int value
) {
this.value
= value
;
}
}
public static Node
getMaxTree(int[] arr
) {
Node
[] nArr
= new Node[arr
.length
];
for (int i
= 0; i
!= arr
.length
; i
++) {
nArr
[i
] = new Node(arr
[i
]);
}
Stack
<Node> stack
= new Stack<>();
HashMap
<Node,Node> lBigMap
= new HashMap<>();
HashMap
<Node,Node> rBigMap
= new HashMap<>();
for (int i
= 0; i
!= nArr
.length
; i
++) {
Node curNode
= nArr
[i
];
while ((!stack
.isEmpty()) && stack
.peek().value
< curNode
.value
) {
popStackSetMap(stack
,lBigMap
);
}
stack
.push(curNode
);
}
while (!stack
.isEmpty()) {
popStackSetMap(stack
,lBigMap
);
}
for (int i
= nArr
.length
- 1; i
!= -1; i
--) {
Node curNode
= nArr
[i
];
while ((!stack
.isEmpty()) && stack
.peek().value
< curNode
.value
) {
popStackSetMap(stack
,rBigMap
);
}
stack
.push(curNode
);
}
while (!stack
.isEmpty()) {
popStackSetMap(stack
,rBigMap
);
}
Node head
= null
;
for (int i
= 0; i
!= nArr
.length
; i
++) {
Node curNode
= nArr
[i
];
Node left
= lBigMap
.get(curNode
);
Node right
= rBigMap
.get(curNode
);
if (left
== null
&& right
== null
) {
head
= curNode
;
} else if (left
== null
) {
if (right
.left
== null
) {
right
.left
= curNode
;
} else {
right
.right
= curNode
;
}
} else if (right
== null
) {
if (left
.left
== null
) {
left
.left
= curNode
;
} else {
left
.right
= curNode
;
}
} else {
Node parent
= left
.value
< right
.value
? left
: right
;
if (parent
.left
== null
) {
parent
.left
= curNode
;
} else {
parent
.right
= curNode
;
}
}
}
return head
;
}
private static void popStackSetMap(Stack
<Node> stack
, HashMap
<Node, Node> map
) {
Node popNode
= stack
.pop();
if (stack
.isEmpty()) {
map
.put(popNode
, null
);
} else {
map
.put(popNode
,stack
.peek());
}
}
public static Node
getMaxTree2(int[] arr
){
Node
[] nArr
= new Node[arr
.length
];
for (int i
= 0; i
< arr
.length
; i
++) {
nArr
[i
] = new Node(arr
[i
]);
}
for (int i
= 0; i
< nArr
.length
; i
++) {
heapfiyInsert(nArr
, i
);
}
for (int i
= 0; i
< nArr
.length
; i
++) {
if (2*i
+1 < nArr
.length
){
nArr
[i
].left
= nArr
[2*i
+1];
}
if (2*i
+2 < nArr
.length
){
nArr
[i
].right
= nArr
[2*i
+2];
}
}
return nArr
[0];
}
static void heapfiyInsert(Node
[] nArr
, int index
){
while (nArr
[index
].value
> nArr
[(index
-1)/2].value
){
swap(nArr
, index
, (index
-1)/2);
index
= (index
-1)/2;
}
}
static void swap(Node
[] nArr
, int a
, int b
){
Node temp
= nArr
[a
];
nArr
[a
] = nArr
[b
];
nArr
[b
] = temp
;
}
public static void main(String
[] args
) {
int[] arr
= new int[]{3,4,1,2};
getMaxTree2(arr
);
}
}
