二叉树及其三种序的递归实现
1）二叉树的节点 2）二叉树的先序、中序、后序 3）递归序加工出三种序的遍历 4）时间复杂度O(n)，额外空间复杂度O(h)，h是二叉树的高度
1 什么是二叉树的先序、中序、后序遍历
这个概念比较简单 参考帖子
2 代码:二叉树的先序、中序、后序遍历
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
public class TreeTraversal {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v) {
val = v;
}
}
public static void preOrder(TreeNode head) {
if (head == null) return;
System.out.print(head.val + " ");
preOrder(head.left);
preOrder(head.right);
}
public static void inOrder(TreeNode head) {
if (head == null) return;
inOrder(head.left);
System.out.print(head.val + " ");
inOrder(head.right);
}
public static void postOrder(TreeNode head) {
if (head == null) return;
postOrder(head.left);
postOrder(head.right);
System.out.print(head.val + " ");
}
public static void main(String[] args) {
TreeNode head = new TreeNode(1);
head.left = new TreeNode(2);
head.right = new TreeNode(3);
head.left.left = new TreeNode(4);
head.left.right = new TreeNode(5);
head.right.left = new TreeNode(6);
head.right.right = new TreeNode(7);
preOrder(head);
System.out.println();
System.out.println("先序遍历递归版");
inOrder(head);
System.out.println();
System.out.println("中序遍历递归版");
postOrder(head);
System.out.println();
System.out.println("后序遍历递归版");
}
}
3 递归序加工出三种序的遍历
递归序：
1
2
3
4
5
6
7
8
public static void f(TreeNode head){
if (head == null) return;
// 位置 1
f(head.left);
// 位置 2
f(head.right);
// 位置 3
}
这个框架是一个典型的递归遍历二叉树的模板，通过在不同位置（上面加了//的地方）插入“处理节点”（比如打印节点值）的代码，可以实现三种遍历方式。
递归本质：每次调用 f 处理一个子树，三个位置决定了根的访问时机。（这3个位置根都会访问到）
- 位置 1（先序）：根最先处理，体现“根-左-右”。
- 位置 2（中序）：根在左子树后、右子树前处理，体现“左-根-右”。
- 位置 3（后序）：根最后处理，体现“左-右-根”。
4 如何理解额外空间复杂度O(h)
想象你是一个探险队长，要遍历一棵二叉树（家谱树），每次探到一个节点，你得记下“下一步去哪儿”或者“回头找谁”。这个记录用的是一个“记事本”（栈），记事本的大小取决于你一次探多深。树的高度 h 就像从树顶到最底层的层数，决定了记事本最多要记多少条。
为什么不是O(n)？
你探树时，记事本不用记全家谱，只记当前探的那条“最深路线”，路线长度最多是树高 h。
