左神算法（一）下修改版

序言：

此篇内容紧跟在左神算法（一）上修改版之后。

左神算法（一）上修改版

左神算法（一）下修改版

左神算法（二）

七、二叉树的基本算法

1.二叉树

2.二叉树的先序、中序、后序遍历

先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树
中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树
后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点

先序、中序、后序遍历要求对每一棵子树都成立。以下图的中序遍历为例：以1作为头节点，4、2、5、1、6、3、7按照左、中、右的顺序遍历节点；若以2作为头节点，4、2、5按照左、中、右的顺序遍历节点.

递归序：递归使得每个节点都会到达三次。

先序遍历：第一次到达节点时就打印。
中序遍历：第二次到达节点时就打印。
后序遍历：第三次到达节点时就打印。

到达第2节点时，向2的左子树执行，执行到4，4的左子树执行，遇到空返回了4，然后去4的右子树执行，遇到空又返回了4，这就是3个4的来历。

3.递归方式实现二叉树的先序、中序、后序遍历

（1）理解递归序
（2）先序、中序、后序都可以在递归序的基础上加工出来
（3）第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序

4.非递归方式实现二叉树的先序、中序、后序遍历

（1）任何递归函数都可以改成非递归
（2）自己设计压栈的来实现

（1）先序遍历：头左右

栈是逆序的，先压右再压左，弹出时就是先弹出左再弹出右。

原则：栈如果不为空

（1）弹出就打印

（2）对于每个节点，如有右孩子，先压入右孩子，之后再到被压入的节点上再看。

（3）对于每个节点，如有左孩子，再压入左孩子，之后再到被压入的节点上再看。

行为：1压入栈，弹出并打印1；3压入栈、2压入栈，弹出并打印2；5压入栈、4压入栈；弹出并打印4、弹出并打印5；弹出并打印3；7压入栈、6压入栈；弹出并打印6，弹出并打印7。

先序遍历结果：1，2，4，5，3，6，7

（2）后序遍历：左右头

栈是逆序的，先压左再压右，弹出时就是先弹出右再弹出左。

原则：栈如果不为空

（1）弹出就打印

（2）对于每个节点，如有左孩子，先压入左孩子，之后再到被压入的节点上再看。

（3）对于每个节点，如右左孩子，再压入右孩子，之后再到被压入的节点上再看。

行为：1压入栈，弹出并打印1；2压入栈、3压入栈，弹出并打印3；6压入栈、7压入栈，弹出并打印7，弹出并打印6；弹出并打印2；4压入栈、5压入栈；弹出并打印5、弹出并打印4。

上述完成后为：头右左[1，3，7，6，2，5，4]。对此我们可以在上述弹出后不打印，而是把其压入另一个新栈。当所有数在旧栈中弹出完毕后，我们再弹出新栈里的数，这样弹出的就是左右头的顺序了，即后序遍历结果：4，5，2，6，7，3，1

（3）中序遍历

头节点不为空，压入栈中，并到当前头节点的左子节点，把左子节点当作头节点，重复上述流程，知道头节点为空停止

原则：栈如果不为空且头节点不为空

（1）整条左边界依次入栈

（2）第一条逻辑无法命中，那么弹出并打印节点，然后来到弹出节点的右树上，继续执行第一条逻辑

行为：1压入栈，2压入栈，4压入栈；弹出并打印4、弹出并打印2；5压入栈；弹出并打印5；弹出并打印1；3压入栈、6压入栈；弹出并打印6、弹出并打印3。7压入栈；弹出并打印7。

中序遍历结果：4，2，5，1，6，3，7

接下来我们再看看后序遍历的炫技版：一个栈实现后序遍历

对于后序遍历的炫技版的解析：

while语句中if条件就是左树没处理的情况下处理左树；else if条件就是右树没处理的情况下处理右树；else条件就是左右两树都处理完了返回。

h的解释：没有弹出打印之前别干扰节点压左边界，弹出打印之后要确保h可以用于标记左右两树有没有弹出打印完。

初始状态下：h指向头节点，stack为null。stack.push(h)使得栈中多了一个元素h。c指向null。

进入while循环后。c=stack.peek()使得c指向了头节点1。

满足if条件进入if语句。stack.push(c.left)使得栈中多了一个元素c.left也就是2 此时栈中有2个元素，从下到上为：1，2

又进入while循环。c=stack.peek()使得c指向了节点2。

满足if条件进入if语句。stack.push(c.left)使得栈中多了一个元素c.left也就是4

此时栈中有3个元素，从下到上为：1，2，4

又进入while循环。c=stack.peek()使得c指向了节点4。

满足else条件进入else语句。

        System.out.print(stack.pop().value + " ");语句使得stack弹出并打印了4.
1

h=c使得h指向了4.

此时栈中有2个元素，从下到上为：1，2

又进入while循环。c=stack.peek()使得c指向了节点2。

满足else if条件进入else if语句。

                stack.push(c.right);使得栈中多了一个元素c.right也就是5
1

此时栈中有3个元素，从下到上为：1，2，5

又进入while循环。c=stack.peek()使得c指向了节点5。

满足else条件进入else语句。

        System.out.print(stack.pop().value + " ");语句使得stack弹出并打印了5.
1

h=c使得h指向了5.

此时栈中有2个元素，从下到上为：1，2

又进入while循环。c=stack.peek()使得c指向了节点2。

满足else条件进入else语句。

        System.out.print(stack.pop().value + " ");语句使得stack弹出并打印了2.
1

h=c使得h指向了2.

此时栈中有1个元素，从下到上为：1

…

5.实现二叉树的按层遍历

（1）其实就是宽度优先遍历，用队列
（2）可以通过设置flag变量的方式，来发现某一层的结束（看题目）

1加入队列；输出并打印1；2、3加入队列；输出并打印2；4、5加入队列；输出并打印3；6、7加入队列；输出并打印4、5、6、7.

代码如下：

package class11;

import java.util.LinkedList;
import java.util.Queue;

public class Code01_LevelTraversalBT {
   

	public static class Node {
   
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
   
			value = v;
		}
	}

	public static void level(Node head) {
   
		if (head == null) {
   
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		while (!queue.isEmpty()) {
   
			Node cur = queue.poll();
			System.out.println(cur.value);

			if (cur.left != null) {
   
				queue.add(cur.left);
			}
			if (cur.right != null) {
   
				queue.add(cur.right);
			}
		}
	}

	public static void main(String[] args) {
   
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		level(head);
		System.out.println("========");
	}

}
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

新增需求：统计二叉树的最大宽度
（1）用Map的机制：
哪一层节点数量最多，宽度最大，节点数量最多的不一定是在最后一层。因此，我们在上述代码中还要加一个机制，我们需要知道每一层的开始或结束。

Queue queue = new LinkedList<>();
queue.add(head);        这两行使头节点被添加到队列中。
levelMap.put(head, 1);意思是head节点在第1层。
int curLevel = 1; 当前层为1层。
int curLevelNodes = 0; 当前层的节点是0个，我们在队列输出时再统计。
int max = 0;所有层的某一层的节点的最大值。
1
2
3
4
5
6

下面进入while循环：

Node cur = queue.poll();弹出节点cur，cur为头节点head，即1.
int curNodeLevel = levelMap.get(cur);levelMap根据cur，cur即head，得到curNodeLevel 为1
1
2

执行第一个if语句：

levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
1
2

执行第二个if语句：

levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
1
2

执行第三个if语句：

curLevelNodes++;
1

下面进入第二次while循环：

Node cur = queue.poll();
1

…

max = Math.max(max, curLevelNodes);max=1
curLevel++;当前层变为2
curLevelNodes = 1;当前层节点变为1
1
2
3

（2）不用Map的机制：

使用Map或不使用Map的代码：

package class11;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Code05_TreeMaxWidth {
   

	public static class Node {
   
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
   
			this.value = data;
		}
	}

	public static int maxWidthUseMap(Node head) {
   
		if (head == null) {
   
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		// levelMap存储的是key 在 哪一层
		HashMap<Node, Integer> levelMap = new HashMap<>();
		levelMap.put(head, 1);
		int curLevel = 1; // curLevel为当前你正在统计哪一层的宽度
		int curLevelNodes = 0; // curLevelNodes为当前层curLevel的目前宽度
		// 更新的所有层的节点的最大值。
		int max = 0;
		while (!queue.isEmpty()) {
   
			Node cur = queue.poll();
			int curNodeLevel = levelMap.get(cur);
			if (cur.left != null) {
   
				levelMap.put(cur.left, curNodeLevel + 1);
				queue.add(cur.left);
			}
			if (cur.right != null) {
   
				levelMap.put(cur.right, curNodeLevel + 1);
				queue.add(cur.right);
			}
			if (curNodeLevel == curLevel) {
   
				curLevelNodes++;
			} else {
   
				max = Math.max(max, curLevelNodes);
				curLevel++;
				curLevelNodes = 1;
			}
		}
		max = Math.max(max, curLevelNodes);
		return max;
	}

	public static int maxWidthNoMap(Node head) {
   
		if (head == null) {
   
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		Node curEnd = head; // 当前层，最右节点是谁
		Node nextEnd = null; // 下一层，最右节点是谁
		int max = 0;
		int curLevelNodes = 0; // 当前层的节点数
		while (!queue.isEmpty()) {
   
			Node cur = queue.poll();
			if (cur.left != null) {
   
				queue.add(cur.left);
				nextEnd = cur.left;
			}
			if (cur.right != null) {
   
				queue.add(cur.right);
				nextEnd = cur.right;
			}
			curLevelNodes++;
			if (cur == curEnd) {
   
				max = Math.max(max, curLevelNodes);
				curLevelNodes = 0;
				curEnd = nextEnd;
			}
		}
		return max;
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
   
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
   
		if (level > maxLevel || Math.random() < 0.5) {
   
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
   
		int maxLevel = 10;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
   
			Node head = generateRandomBST(maxLevel, maxValue);
			if (maxWidthUseMap(head) != maxWidthNoMap(head)) {
   
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");

	}

}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

6.二叉树的序列化和反序列化

（1）可以用先序或者后序或者按层遍历，来实现二叉树的序列化。
（2）用了什么方式序列化，就用什么样的方式反序列化。

（1）为什么要序列化？

如下图，下面的两棵树先序、中序、后序的结果都是1，1，1.然而它们对应的结构是不同的。所以如果使用先序、中序、后序的方式记录顺序的话没有办法做到彻底还原树结构。

因此，我们不要忽略空节点。

（2）先序方式序列化：头左右

上图（a图）序列化后的：[1,1,null,1,null,null,null]

上图（b图）序列化后的：[1,null,1,1,null,null,null]

反序列化：也按照头左右方式还原。

（3）按层序列化：

代码如下：

package class11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Code02_SerializeAndReconstructTree {
   
    /*
     * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
     * 以下代码全部实现了。
     * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
     * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
     * 比如如下两棵树
     *         __2
     *        /
     *       1
     *       和
     *       1__
     *          \
     *           2
     * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
     *       
     * */
	public static class Node {
   
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
   
			this.value = data;
		}
	}

	// 先序方式序列化
	public static Queue<String> preSerial(Node head) {
   
		Queue<String> ans = new LinkedList<>();
		pres(head, ans);
		return ans;
	}

	// 先序方式序列化
	public static void pres(Node head, Queue<String> ans) {
   
		if (head == null) {
   
			ans.add(null);
		} else {
   
			ans.add(String.valueOf(head.value));
			pres(head.left, ans);
			pres(head.right, ans);
		}
	}

	// 中序方式序列化
	public static Queue<String> inSerial(Node head) {
   
		Queue<String> ans = new LinkedList<>();
		ins(head, ans);
		return ans;
	}

	// 中序方式序列化
	public static void ins(Node head, Queue<String> ans) {
   
		if (head == null) {
   
			ans.add(null);
		} else {
   
			ins(head.left, ans);
			ans.add(String.valueOf(head.value));
			ins(head.right, ans);
		}
	}

	// 后序方式序列化
	public static Queue<String> posSerial(Node head) {
   
		Queue<String> ans = new LinkedList<>();
		poss(head, ans);
		return ans;
	}

	// 后序方式序列化
	public static void poss(Node head, Queue<String> ans) {
   
		if (head == null) {
   
			ans.add(null);
		} else {
   
			poss(head.left, ans);
			poss(head.right, ans);
			ans.add(String.valueOf(head.value));
		}
	}

	// 先序方式反序列化
	public static Node buildByPreQueue(Queue<String> prelist) {
   
		if (prelist == null || prelist.size() == 0) {
   
			return null;
		}
		return preb(prelist);
	}

	// 先序方式反序列化
	public static Node preb(Queue<String> prelist) {
   
		String value = prelist.poll();
		if (value == null) {
   
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		head.left = preb(prelist);
		head.right = preb(prelist);
		return head;
	}

	// 后序方式反序列化
	public static Node buildByPosQueue(Queue<String> poslist) {
   
		if (poslist == null || poslist.size() == 0) {
   
			return null;
		}
		// 左右中  ->  stack(中右左)
		Stack<String> stack = new Stack<>();
		while (!poslist.isEmpty()) {
   
			stack.push(poslist.poll());
		}
		return posb(stack);
	}

	// 后序方式反序列化
	public static Node posb(Stack<String> posstack) {
   
		String value = posstack.pop();
		if (value == null) {
   
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		head.right = posb(posstack);
		head.left = posb(posstack);
		return head;
	}

	// 按层序列化
	public static Queue<String> levelSerial(Node head) {
   
		Queue<String> ans = new LinkedList<>();
		if (head == null) {
   
			ans.add(null);
		} else {
   
			ans.add(String.valueOf(head.value));// 加入队列的时候序列化
			Queue<Node> queue = new LinkedList<Node>();
			queue.add(head);
			while (!queue.isEmpty()) {
   
				head = queue.poll(); // head 父   子
				if (head.left != null) {
   // 既序列化也加队列
					ans.add(String.valueOf(head.left.value));
					queue.add(head.left);
				} else {
    // 只序列化
					ans.add(null);
				}
				if (head.right != null) {
    // 既序列化也加队列
					ans.add(String.valueOf(head.right.value));
					queue.add(head.right);
				} else {
    // 只序列化
					ans.add(null);
				}
			}
		}
		return ans;
	}

	// 按层反序列化
	public static Node buildByLevelQueue(Queue<String> levelList) {
   
		if (levelList == null || levelList.size() == 0) {
   
			return null;
		}
		Node head = generateNode(levelList.poll());
		Queue<Node> queue = new LinkedList<Node>();
		if (head != null) {
   
			queue.add(head);
		}
		Node node = null;
		while (!queue.isEmpty()) {
   
			node = queue.poll();
			node.left = generateNode(levelList.poll());
			node.right = generateNode(levelList.poll());
			if (node.left != null) {
   
				queue.add(node.left);
			}
			if (node.right != null) {
   
				queue.add(node.right);
			}
		}
		return head;
	}

	// 按层反序列化
	public static Node generateNode(String val) {
   
		if (val == null) {
   
			return null;
		}
		return new Node(Integer.valueOf(val));
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
   
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
   
		if (level > maxLevel || Math.random() < 0.5) {
   
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	// for test
	public static boolean isSameValueStructure(Node head1, Node head2) {
   
		if (head1 == null && head2 != null) {
   
			return false;
		}
		if (head1 != null && head2 == null) {
   
			return false;
		}
		if (head1 == null && head2 == null) {
   
			return true;
		}
		if (head1.value != head2.value) {
   
			return false;
		}
		return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
	}

	// for test
	public static void printTree(Node head) {
   
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
   
		if (head == null) {
   
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
   
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
   
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
   
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		System.out.println("test begin");
		for (int i = 0; i < testTimes; i++) {
   
			Node head = generateRandomBST(maxLevel, maxValue);
			Queue<String> pre = preSerial(head);
			Queue<String> pos = posSerial(head);
			Queue<String> level = levelSerial(head);
			Node preBuild = buildByPreQueue(pre);
			Node posBuild = buildByPosQueue(pos);
			Node levelBuild = buildByLevelQueue(level);
			if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
   
				System.out.println("Oops!");
			}
		}
		System.out.println("test finish!");
		
	}
}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333

7.如何设计一个打印整棵树的打印函数

上图是按照对于每棵树都是先右，再头，再左的遍历方式，旋转90度就是平常见的样子。

同时这么打印还有的好处是：数字对齐问题很容易实现；花费时间少。

代码运行结果和对照：

代码如下：

package class11;

public class Code04_PrintBinaryTree {
   

	public static class Node {
   
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
   
			this.value = data;
		}
	}

	public static void printTree(Node head) {
   
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
   
		if (head == null) {
   
			return;
		}
		printInOrder(head.right, height + 1, "v", len);

		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);

		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
   
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
   
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
   
		Node head = new Node(1);
		head.left = new Node(-222222222);
		head.right = new Node(3);
		head.left.left = new Node(Integer.MIN_VALUE);
		head.right.left = new Node(55555555);
		head.right.right = new Node(66);
		head.left.left.right = new Node(777);
		printTree(head);

		head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.right.left = new Node(5);
		head.right.right = new Node(6);
		head.left.left.right = new Node(7);
		printTree(head);

		head = new Node(1);
		head.left = new Node(1);
		head.right = new Node(1);
		head.left.left = new Node(1);
		head.right.left = new Node(1);
		head.right.right = new Node(1);
		head.left.left.right = new Node(1);
		printTree(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
73
74
75
76
77
78
79
80
81
82
83
84
85

8.题目1：

注意：很多树都会加一个往上去的指针，比如红黑树。刷题时碰到二叉树默认只有左右两个指针，除非特别声明。

后继节点：一棵二叉树中在中序遍历的序列中某一个节点的下一个节点。

后继节点的举例：

（1）一种普遍的解法：

已知节点x，求x的后继节点。我们可以先通过x找到树的头部，然后我们通过头部中序遍历这个树，得到一个序列，然后我们在序列中已知x找到x的后继节点。

上述方法的时间复杂度是O(N)。假设某一个节点到它结束的实际距离是k，我们想要试图让时间复杂度变为最多O(k)，而不是每次都是O(k)。

（2）更优解：

几种情况：

若某一节点x，有右子树，那么很明显，x的右子树就是x的后继节点。

若某一节点x，没有右子树，我们考虑它的后继节点：

h没有右树，其后继节点是d；

i没有右树，其后继节点是b；

j没有右树，其后继节点是e；

k没有右树，其后继节点是a；

原则：
若某一节点x有右子树，那么其右子树的最做左节点就是x的后继节点。

若某一节点x没有右子树，那么x向上找其父节点，若x是其父节点的右子节点，继续找父节点，直道x是某一节点y的左子节点再停止，y就是x的后继节点。另一个角度来看，头节点为？，头节点的左子树的最右边的节点为x，？就是x的后继节点，因为中序遍历为左中右的顺序。

如果一个节点没有后继节点，那么这个节点一定是整棵树上最右边的节点。

代码如下：

package class11;

public class Code06_SuccessorNode {
   

	public static class Node {
   
		public int value;
		public Node left;
		public Node right;
		public Node parent;

		public Node(int data) {
   
			this.value = data;
		}
	}

	public static Node getSuccessorNode(Node node) {
   
		if (node == null) {
   
			return node;
		}
		if (node.right != null) {
   
			return getLeftMost(node.right);
		} else {
    // 无右子树
			Node parent = node.parent;
			while (parent != null && parent.right == node) {
    // 当前节点是其父亲节点右孩子
				node = parent;
				parent = node.parent;
			}
			return parent;
		}
	}

	public static Node getLeftMost(Node node) {
   
		if (node == null) {
   
			return node;
		}
		while (node.left != null) {
   
			node = node.left;
		}
		return node;
	}

	public static void main(String[] args) {
   
		Node head = new Node(6);
		head.parent = null;
		head.left = new Node(3);
		head.left.parent = head;
		head.left.left = new Node(1);
		head.left.left.parent = head.left;
		head.left.left.right = new Node(2);
		head.left.left.right.parent = head.left.left;
		head.left.right = new Node(4);
		head.left.right.parent = head.left;
		head.left.right.right = new Node(5);
		head.left.right.right.parent = head.left.right;
		head.right = new Node(9);
		head.right.parent = head;
		head.right.left = new Node(8);
		head.right.left.parent = head.right;
		head.right.left.left = new Node(7);
		head.right.left.left.parent = head.right.left;
		head.right.right = new Node(10);
		head.right.right.parent = head.right;

		Node test = head.left.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left.left.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.left.right.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right.left.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
		test = head.right.right; // 10's next is null
		System.out.println(test.value + " next: " + getSuccessorNode(test));
	}

}
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

多想一步：如何求前驱节点？（也是在中序遍历中某一节点的前一个节点）。思维与上类似。

9.题目2（前几年流行）

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。
例如：N=1时，打印： down N = 2时，打印：down down up

初始纸条：没有任何折痕

这样对折一次：开口往上的

打开后：

如图折痕我们称为凹折痕。

凹折痕上画条线并写上字：1凹

恢复程成折一次的样子：开口往上的

进行第二次对折：开口往上的

折完之后打开：此时从上往下有：凹折痕（第二次形成的），凹折痕（第一次形成的并且有标记为1凹），凸折痕（第二次形成的）

之后我们再进行标记：从上往下为：2凹，1凹，2凸

再还原成折两次的样子：开口往上的

再折叠第三次：开口往上的

再打开：

再进行标记：从上往下为：3凹，2凹，3凸，1凹，3凹，2凸，3凸。

一个规律：
当只有1个折痕后，那个折痕是凹折痕，后续每次的折法都跟折第一次时一样，开头都朝上。再折第二次，那么在第一次凹折痕（1凹）上面出现一个凹折痕（2凹），第一次凹折痕（1凹）下面出现一个个凸折痕（2凸）。再折第三次，我们发现再2凹上方出现3凹1，2凹下面出现3凸1；前面是1凹的上面，后面是1凹的下面；2凸上方出现3凹2，2凸下方出现3凸2。
即每一次折（>=2）留下的折痕都会在每一个上一次的折痕的上方出现凹折痕、下方出现凸折痕。

要求：从上往下打印所有折痕的方向

非二叉树法（这种方法浪费空间）：
大致思路：若折N次，会产生(2 ^ N) -1个折痕。创建一个(2 ^ N) -1长度的数组，填满这个数组并遍历。这个额外空间复杂度是O(2 ^ N -1)

二叉树法：

二叉树法代码如下：

package class11;

public class Code07_PaperFolding {
   

	public static void printAllFolds(int N) {
   
		// 传入1代表从头节点开始
		process(1, N, true);
		System.out.println();
	}

	// 当前你来了一个节点，脑海中想象的！
	// 这个节点在第i层，一共有N层，N固定不变的
	// 这个节点如果是凹的话，down = T
	// 这个节点如果是凸的话，down = F
	// 函数的功能：中序打印以你想象的节点为头的整棵树！
	// i是第几层的节点。N是固定参数，表示最多有几层。down表示此层的点是否为凹折痕的点。
	// 递归法模拟了二叉树遍历，但是这棵树没有实际产生过！！！
	public static void process(int i, int N, boolean down) {
   
		if (i > N) {
   
			return;
		}
		process(i + 1, N, true);
		System.out.print(down ? "凹 " : "凸 ");
		process(i + 1, N, false);
	}

	public static void main(String[] args) {
   
		int N = 4;
		printAllFolds(N);
	}
}
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

为什么代码中没有建出二叉树却能实现二叉树打印呢？
因为这棵树有明确规则，左树节点都是凹，右树节点都是凸，头节点默认凹。这种明确规则的树当然不需要完全建出这棵树才能打印。这个额外空间复杂度是O(N)。

八、二叉树的递归套路

1.二叉树的递归套路

可以解决面试中绝大多数的二叉树问题，尤其是树型dp问题。
本质是利用递归遍历二叉树的便利性。

整套课程小技巧多如牛毛。大主线就两个，一个是二叉树的递归套路，还有一个是暴力递归改动态规划的套路（任何动态规划题目都能解）。

二叉树的递归套路实际就是在树上做动态规划，动态规划就是用空间换时间的方式。上述的绝大多数即95%以上。二叉树的题目能用二叉树递归套路的占95%以上。递归遍历二叉树使每个节点都可以到达3次。

2.二叉树的递归套路

上述所言的左树和右树是头节点的左树和头节点的右树的省略。

或者说默认认为左树和右树是头节点的左树和头节点的右树。

第（1）点默认符合。

3.给定一个二叉树的头节点head，返回这棵二叉树是不是平衡二叉树。

从要求来看，我们可知：左子树、右子树是能给头节点信息的，head就是X。满足二叉树的递归套路的第（1）点。

平衡二叉树：二叉树中每一棵子树的左树和右树的高度差不超过1。

由题可得：二叉树中头节点的左树要是平衡的；头节点的右树要是平衡的；头节点的左树和为头节点的右树的高度差不超过1.X就是头节点。二叉树的递归套路的第（2）点。

二叉树的递归套路的第（3）点，即头节点向子树和右树要什么样的信息：头节点的左树平衡与否和高度多少；头节点的右树平衡与否和高度多少。这一点的代码如下：

二叉树的递归套路的第（4）点：把左树信息和右树信息求全集，这里我们的左树和右树信息一样的，所以没有求全集。

代码如下：

package class12;

public class Code03_IsBalanced {
   

	public static class Node {
   
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
   
			this.value = data;
		}
	}

	public static boolean isBalanced1(Node head) {
   
		boolean[] ans = new boolean[1];
		ans[0] = true;
		process1(head, ans);
		return ans[0];
	}

	public static int process1(Node head, boolean[] ans) {
   
		if (!ans[0] || head == null) {
   
			return -1;
		}
		int leftHeight = process1(head.left, ans);
		int rightHeight = process1(head.right, ans);
		if (Math.abs(leftHeight - rightHeight) > 1) {
   
			ans[0] = false;
		}
		return Math.max(leftHeight, rightHeight) + 1;
	}

	public static boolean isBalanced2(Node head) {
   
		return process(head).isBalanced;
	}

	// 左、右树要求一样，Info信息返回的结构体
	public static class Info{
   
		public boolean isBalanced;
		public int height;
		
		public Info(boolean i, int h) {
   
			isBalanced = i;
			height = h;
		}
	}
	
	public static Info process(Node x) {
   
		if(x == null) {
   
			return new Info(true, 0);
		}
		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);

		int height = Math.max(leftInfo.height, rightInfo.height)  + 1;
		boolean isBalanced = true;

		if(!leftInfo.isBalanced) {
   
			isBalanced = false;
		}
		if(!rightInfo.isBalanced) {
   
			isBalanced = false;
		}
		if(Math.abs(leftInfo.height - rightInfo.height) > 1) {
   
			isBalanced = false;
		}

		return new Info(isBalanced, height);
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
   
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
   
		if (level > maxLevel || Math.random() < 0.5) {
   
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
   
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
   
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isBalanced1(head) != isBalanced2(head)) {
   
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}
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
117
118
119
120
121
122

4.给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离。

举例：a到b的距离是3，c到d的距离是4。（距离算上自己本身那一节点）

误区：最大距离不是最左到最右，下图是反例：

某个视角来看，最大距离有两种情况（此处进行了二叉树的递归套路的第（2）点）：
一种是不通过头节点X，最大距离与X无关。若无关，那么最大距离是左树中最大距离和右树中最大距离两者的最大值。

一种是通过头节点X，最大距离与X有关。左树上离头节点最远的点到右树上离头节点最远的点，即左树高+1（1是头节点自己）+右树高度。

二叉树的递归套路的第（3）点：
我们需要左树返回他的最大距离和高度，右树返回他的最大距离和高度。

递归代码：

对于递归代码的解析：

有以上几个节点， f(a)调用f(b)，f(b)调用f(d)。f(d)向左调用为空，返回到f(d)，左子节点到自己的距离是0，但是自己到自己的距离是1，最大高度也是1。f(d)向右调用为空，返回到f(d)，然后再向上返回。

代码如下（有暴力法也有二叉树法，二叉树法有动态规划的思路。）：

package class12;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Code06_MaxDistance {
   

	public static class Node {
   
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
   
			this.value = data;
		}
	}

	// 上方是暴力方法
	public static int maxDistance1(Node head) {
   
		if (head == null) {
   
			return 0;
		}
		ArrayList<Node> arr = getPrelist(head);
		HashMap<Node, Node> parentMap = getParentMap(head);
		int max = 0;
		for (int i = 0; i < arr.size(); i++) {
   
			for (int j = i; j < arr.size(); j++) {
   
				max = Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));
			}
		}
		return max;
	}

	public static ArrayList<Node> getPrelist(Node head) {
   
		ArrayList<Node> arr = new ArrayList<>();
		fillPrelist(head, arr);
		return arr;
	}

	public static void fillPrelist(Node head, ArrayList<Node> arr) {
   
		if (head == null) {
   
			return;
		}
		arr.add(head);
		fillPrelist(head.left, arr);
		fillPrelist(head.right, arr);
	}

	public static HashMap<Node, Node> getParentMap(Node head) {
   
		HashMap<Node, Node> map = new HashMap<>();
		map.put(head, null);
		fillParentMap(head, map);
		return map;
	}

	public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
   
		if (head.left != null) {
   
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
   
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

	public static int distance(HashMap<Node, Node> parentMap, Node o1, Node o2) {
   
		HashSet<Node> o1Set = new HashSet<>();
		Node cur = o1;
		o1Set.add(cur);
		while (parentMap.get(cur) != null) {
   
			cur = parentMap.get(cur);
			o1Set.add(cur);
		}
		cur = o2;
		while (!o1Set.contains(cur)) 
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

相关阅读:
计算机毕设（附源码）JAVA-SSM基于web在线考试系统
 Redis 缓存数据库
 Java入门------static关键字和静态属性、方法
 CIIS 2023丨聚焦文档图像处理前沿领域，合合信息AI助力图像处理与内容安全保障
 云小课｜MRS基础原理之Oozie任务调度
 基于JavaWeb的电影订票及评论网站设计与实现
 拨开发展迷雾，将“智慧”嵌入全业务场景【2022戴尔科技峰会预告】
【21天学习挑战赛】荷兰国旗问题到快速排序
 手把手教你配置vscode的c++开发环境（wsl + 远程)
[old]TeamDev DotNetBrowser Crack
原文地址：https://blog.csdn.net/weixin_52364990/article/details/123010448