MaxTree

一个数组的MaxTree定义如下：
数组必须没有重复元素；
MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点；
包括MaxTree树在内并且在其中的每一颗子树上，值最大的节点都是树的头；

给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，时间复杂度O(N)，额外空间复杂度O(N)

思路

该树并不是堆，因为不是平衡的，只是有性质任意子树的头结点比任何结点的值都大

  • leftMap和rightMap
    本题使用leftMap和rightMap分别记录当前结点左边第一个比它大的结点和当前结点右边第一个比它大的结点
    这个记录过程是利用栈来实现的，栈中必须满足从堆底到堆顶是从小到大的顺序
    先从左向右遍历，如果当前结点比堆顶小就直接进入，否则就弹出，直到可以进入为止，弹出的过程就记录比当前结点大的结点
    然后从右向左遍历，同理

  • 建树
    建树的过程就是利用leftMap和rightMap
    遍历所有结点，找到其lNode和rNode

    • 都不空，选择较小的为父，因为较大的可能被选为根节点
    • 有一个空，选择不空的为父
    • 都空，自己就是头

代码

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
public static class Node {
	int value;
	Node left;
	Node right;
	public Node(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}
public static Node getMaxTree(int[] a) {
	if (a == null || a.length == 0) {
		return null;
	}
	Stack<Node> stack = new Stack<Node>();
	//右边比第一个比当前结点大
	HashMap<Node, Node> rightMap = new HashMap<Node, Node>();
	//左边比第一个比当前结点大
	HashMap<Node, Node> leftMap = new HashMap<Node, Node>();
	
	//这里必须将所有结点存储到一个数组中，然后以后对node数组取出，修改，才能地址修改
	//如果不这样做，后续都对a建立新的结点，那么修改左右子树的每个结点都是新结点，不能保存原来的修改
	Node[] arr = new Node[a.length];
	for (int i = 0; i < a.length; i++) {
		arr[i] = new Node(a[i]);
	}
	// 初始化leftMap，记录左边第一个大
	for (int i = 0; i < arr.length; i++) {
		// Node cur = new Node(arr[i]);
		//对数组中的值取出，操作，这样才能保存修改
		Node cur = arr[i];
		//比当前结点小的pop
		while (!stack.empty() && stack.peek().value <= arr[i].value) {
			popSetMap(stack, leftMap);
		}
		// 比当前元素小的全部被pop后，放入
		stack.push(cur);
	}
	// 栈中可能会有剩余元素
	while (!stack.empty()) {
		popSetMap(stack, leftMap);
	}
	// 初始化rightMap
	for (int i = arr.length - 1; i >= 0; i--) {
		// Node cur = new Node(arr[i]);
		Node cur = arr[i];
		while (!stack.empty() && stack.peek().value <= arr[i].value) {
			popSetMap(stack, rightMap);
		}
		stack.push(cur);
	}
	while (!stack.empty()) {
		popSetMap(stack, rightMap);
	}
	System.out.println("rightMap:");
	PrintHashMap(rightMap);
	System.out.println("leftMap:");
	PrintHashMap(leftMap);
	// 建立树
	Node head = null;
	for (int i = 0; i < arr.length; i++) {
		// Node node = new Node(arr[i]);
		//仍然对node数组操作，左右子树的信息才能保存
		Node node = arr[i];
		Node lNode = rightMap.get(node);
		Node rNode = leftMap.get(node);
		//左右都没有比当前大的，说明最大，是根节点
		if (lNode == null && rNode == null) {
			head = node;
		} else if (lNode == null && rNode != null) {
			if (rNode.left == null) {
				rNode.left = node;
			} else {
				rNode.right = node;
			}
		} else if (lNode != null && rNode == null) {
			if (lNode.left == null) {
				lNode.left = node;
			} else {
				lNode.right = node;
			}
		} else {
			//左右都有比当前大的，选择较小的当做父亲节点
			Node parent = lNode.value < rNode.value ? lNode : rNode;
			if (parent.left == null) {
				parent.left = node;
			} else {
				parent.right = node;
			}
		}
	}
	return head;
}
public static void popSetMap(Stack<Node> stack, HashMap<Node, Node> hashMap) {
	Node node = stack.pop();
	// stack内是按照栈底到栈顶从大到小的顺序，因此栈底小，栈顶大
	// 相邻靠上的元素的第一个比他大的一定是他的下一个
	if (stack.empty()) {
		hashMap.put(node, null);
	} else {
		hashMap.put(node, stack.peek());
	}
}