用BST的后序遍历数组构造出原始BST_bst后序遍历还原

一、题目

用BST的后序遍历数组构造出原始BST

二、实现

如下面代码，process0()为原始方法，时间复杂度为O(n^2),process1为采用了二分查找法优化后的优化方法，使得时间复杂度低至O(nlogn)

                                   bug积累
  1） 凡是把一个整体，一分为n个小部分，例如二分查找法、将树分为左树和右数的时候容易出现堆溢出情况(无限循环)，所以写完算法的时候要注意模拟边界情况。
  2）树是由结点对象组合而成的，对于对象问题一定要考虑到null，容易出现空指针异常。
1
2
3

class Node {
	public Node(int i) {
		// TODO Auto-generated constructor stub
		this.value = i;
	}

	Node left;
	Node right;
	int value;
}

public class FormPosArrToBST {
	public static void main(String[] args) {
		int[] posArr = { 2, 4, 3, 6, 8, 7, 5 };
		int[] posArr1 = { 6, 7, 8, 5 };
		Node head = process0(posArr, 0, posArr.length - 1);
		Node head1 = process1(posArr1, 0, posArr1.length - 1);
		postorderTraversal(head1);
	}

	private static Node process1(int[] posArr, int l, int r) {
		// TODO Auto-generated method stub
		if (l > r)
			return null;
		Node head = new Node(posArr[r]);
		if (l == r)
			return head;
		// 利用二分查找找到m指针的位置
		int pl = l;
		int pr = r - 1;
		while (pl < pr) {
			// 移位运算符比算数运算符/在底层更加的简单！
			int pTemp = pl + ((pr - pl + 1) >> 1);
			if (posArr[pTemp] > posArr[r])
				pr = pTemp - 1;
			else
				pl = pTemp;
		}
		if (posArr[pl] > posArr[r])
			pl--;
		head.left = process1(posArr, l, pl);
		head.right = process1(posArr, pl + 1, r - 1);
		return head;
	}

	private static void postorderTraversal(Node head) {
		// TODO Auto-generated method stub
		if (head == null)
			return;
		postorderTraversal(head.left);
		System.out.println(head.value);
		postorderTraversal(head.right);
	}

	private static Node process0(int[] posArr, int l, int r) {
		// TODO Auto-generated method stub
		Node head = new Node(posArr[r]);
		if (l > r)
			return null;
		if (l == r)
			return head;
		int m = l - 1;
		for (int i = l; i < r; i++) {
			if (posArr[i] < posArr[r])
				m = i;
		}
		head.left = process0(posArr, l, m);
		head.right = process0(posArr, m + 1, r - 1);
		return head;
	}
}
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