基础结构
1
2
3
4
5
6
7
8
9
10
11
public class Code_10 {
// 简单二叉树节点定义
public static class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int v) { val = v; }
public TreeNode(int v, TreeNode l, TreeNode r) {
val = v; left = l; right = r;
}
}
递归遍历
先序遍历
先压头节点，然后弹出头节点，再依次加入右节点和左节点
先序： 根->左->右
1
2
3
4
5
6
7
8
9
// 先序（递归）
public static void preOrderRec(TreeNode head){
if (head == null) return;
System.out.print(head.val + " ");
preOrderRec(head.left);
preOrderRec(head.right);
}
中序遍历
中序：左->根->右
- 子树头左边界进站（处理完）
- 栈弹出节点打印，节点右数重复步骤1）
- 没子树且栈空
1
2
3
4
5
6
7
8
9
// 中序（递归）
public static void inOrderRec(TreeNode head){
if (head == null) return;
inOrderRec(head.left);
System.out.print(head.val + " ");
inOrderRec(head.right);
}
后序遍历
后序：左->右->根
- 因为先序是-中左右
- 所以先序‘是-中右左
- 故后序是-左右中
1
2
3
4
5
6
7
// 后序（递归）
public static void postOrderRec(TreeNode head){
if (head == null) return;
postOrderRec(head.left);
postOrderRec(head.right);
System.out.print(head.val + " ");
}
用栈实现遍历
先序遍历（栈）
借助栈模拟：
压根节点；
弹出一个节点就打印；
先压右子再压左子（保证左子先处理）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 先序（迭代，栈）
public static void preOrderIter(TreeNode head){
if (head == null) { System.out.println(); return; }
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()){
TreeNode cur = stack.pop();
System.out.print(cur.val + " ");
if (cur.right != null) stack.push(cur.right);
if (cur.left != null) stack.push(cur.left);
}
System.out.println();
}
中序遍历（栈）
一路左压到底：
- 当前指针不停向左下走并入栈；
- 左尽后，弹出栈顶打印，转向其右子树；
- 重复 1）和 2），直到“栈空且指针为空”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 中序（迭代，栈）
public static void inOrderIter(TreeNode head){
Stack<TreeNode> stack = new Stack<>();
while (head != null || !stack.isEmpty()){
if (head != null){
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.val + " ");
head = head.right;
}
}
System.out.println();
}
后序遍历（两个栈）
利用“先序是 中左右，若改成 中右左 再逆序，就得到 左右中（后序）”。 实现：
stack 做“改造先序”的入栈弹栈；
collect 收集弹出的顺序；
最后 collect 逐个弹出即为后序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 后序（迭代，两个栈）
public static void postOrderTwoStacks(TreeNode head){
if (head == null) { System.out.println(); return; }
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> collect = new Stack<>();
stack.push(head);
while (!stack.isEmpty()){
TreeNode cur = stack.pop();
collect.push(cur);
if (cur.left != null) stack.push(cur.left);
if (cur.right != null) stack.push(cur.right);
}
while (!collect.isEmpty()){
System.out.print(collect.pop().val + " ");
}
System.out.println();
}
后序遍历（一个栈）
思路（关键是“最后访问节点”）： 维护 lastVisited：记录上一次被打印的节点。循环不变式：
观察栈顶 cur：
若能继续向左（左子存在且未处理过），先压左；
否则若能向右（右子存在且未处理过），压右；
否则（左右都没有或都处理过），打印自己并弹出，lastVisited = 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
// 后序（迭代，一个栈）
//如果始终没有打印过节点，h就一直是头节点
//一旦打印过节点，h就变成打印节点
//之后h的含义：上一次打印的节点
public static void postOrderOneStack(TreeNode head){
if (head != null){
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()){
TreeNode cur = stack.peek();
if(cur.left != null
&& head != cur.left
&& head != cur.right){
//有左数且左树没被处理过
stack.push(cur.left);
}else if(cur.right !=null
&& head != cur.right){
//有右树且右树没处理过
stack.push(cur.right);
}else{
//左树，右树 没有 或者都处理过了
System.out.print(cur.val + "");
head = stack.pop();
}
}
}
}