二叉树的遍历。
准备工作：二叉树节点定义
首先，咱们得有个树节点。这个很简单，一个值，两个指针，分别指向左、右孩子。
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
我们要实现的目标就是，给定一个TreeNode root，分别用先序、中序、后序三种顺序，打印出所有节点的值。
先序遍历：头 -> 左 -> 右
中序遍历：左 -> 头 -> 右
后序遍历：左 -> 右 -> 头
解法一：递归——最符合直觉的上帝视角
一提到树，我的第一反应就是递归。为什么？因为树的结构定义本身就是递归的：一个节点，加上它的左子树和右子树，而它的子树本身也是一棵树。这种结构简直就是为递归量身定做的。
递归的写法，本质上就是你把自己当成一个“上帝”，你只需要规定好在当前这个节点上，你要做什么，然后把它的左右孩子当成 똑같은 문제（同一个问题）扔给下一层处理就行了。
思路：
确定递归函数的作用：我们的函数
process(TreeNode node)目的就是遍历以node为头的整棵树。确定终止条件 (Base Case)：如果当前节点是
null，说明这棵“树”是空的，直接return就行了。这是递归的出口，没有它就会无限循环，直接栈溢出。确定单层逻辑：根据三种遍历顺序，在函数里安排打印
node.val的时机。先序：一进函数，二话不说，先打印当前节点的值。然后，把左孩子扔给递归，再把右孩子扔给递归。
中序：一进函数，先沉住气，把左孩子扔给递归。等左边的都处理完了，再打印当前节点的值。最后，再把右孩子扔给递归。
后序：一进函数，啥也别干，先把左孩子扔给递归，再把右孩子扔给递归。等左右两边都彻底搞定了，最后再打印当前节点的值。
代码实现：
// 先序遍历
public void preorder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " "); // 1. 打印头
preorder(root.left); // 2. 递归左
preorder(root.right); // 3. 递归右
}
// 中序遍历
public void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left); // 1. 递归左
System.out.print(root.val + " "); // 2. 打印头
inorder(root.right); // 3. 递归右
}
// 后序遍历
public void postorder(TreeNode root) {
if (root == null) {
return;
}
postorder(root.left); // 1. 递归左
postorder(root.right); // 2. 递归右
System.out.print(root.val + " "); // 3. 打印头
}
评价：
优点：代码极其简洁，逻辑清晰，完美地利用了树的递归结构。面试时能写出这个，说明基本功是合格的。
缺点：当树的深度非常大时，递归调用会占用大量的栈空间，可能导致
StackOverflowError。所以，这是一个在思维上很优雅，但在工程上有潜在风险的解法。
解法二：迭代——手动模拟递归的调用栈
既然递归的本质是利用了系统的函数调用栈，那我们能不能自己搞一个栈，手动模拟这个过程呢？当然可以。这个思路，就是从“上帝视角”回归到了“凡人视角”，一步一步地走。
这个方法能让你更深刻地理解遍历的本质，也是面试中考察你对数据结构掌握程度的绝佳方式。
1. 先序遍历（迭代）
思路： 先序是“头、左、右”。这个顺序用栈来实现最简单。
准备一个栈，先把头节点
root压进去。当栈不为空时，循环执行： a. 弹出栈顶节点
cur，打印它的值。 b. 关键：先把cur的右孩子压入栈（如果不为空）。 c. 再把cur的左孩子压入栈（如果不为空）。
为什么要先压右再压左？因为栈是“后进先出”（LIFO），我们后压进去的左孩子，会先被弹出来处理，这就完美实现了“头、左、右”的顺序。
代码实现：
public void preorderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
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);
}
}
}
2. 中序遍历（迭代）
思路： 中序是“左、头、右”。这个稍微复杂一点。它的核心思想是：一路向左，走到尽头，处理一个，再转向右。
准备一个栈。
用一个指针
cur指向root。当
cur不为null或者栈不为空时，循环： a. 如果cur不为null，说明当前节点还有左路可以走。把cur压入栈，然后cur移动到它的左孩子 (cur = cur.left)。一直重复这个操作，直到cur为null，这表示我们已经把一条左链上的所有节点都压栈了。 b. 如果cur为null，说明左边走到底了。从栈里弹出一个节点，打印它的值。然后，让cur指向这个弹出节点的右孩子 (cur = popNode.right)，开始处理右子树。
代码实现：
public void inorderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right;
}
}
}
3. 后序遍历（迭代）
思路： 后序是“左、右、头”。直接模拟这个顺序非常麻烦。但我们可以耍个小聪明。 观察一下先序遍历“头、左、右”，如果我们稍微改一下，变成“头、右、左”，这个实现起来是不是和先序一模一样？只需要把压栈顺序从“先右后左”改成“先左后右”就行了。
得到“头、右、左”这个序列后，你发现了什么？把它整个逆序一下，不就是“左、右、头”了嘛！
所以，后序遍历的迭代解法，最骚的思路就是：
模仿先序遍历，搞出一个“头、右、左”的遍历序列。
在遍历过程中，不直接打印，而是把结果存到一个集合或者另一个栈里。
最后把这个集合/栈逆序输出。
代码实现： 用两个栈，一个用来遍历，一个用来收集结果。
public void postorderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>(); // 辅助栈，用来存储逆序结果
s1.push(root);
while (!s1.isEmpty()) {
TreeNode cur = s1.pop();
s2.push(cur); // 弹出的节点直接入s2
if (cur.left != null) {
s1.push(cur.left);
}
if (cur.right != null) {
s1.push(cur.right);
}
}
// s2中的顺序就是后序遍历的正确顺序
while (!s2.isEmpty()) {
System.out.print(s2.pop().val + " ");
}
}
评价：
优点：解决了递归可能导致的栈溢出问题。代码量稍大，但逻辑更可控。能写出这套非递归代码，面试官会觉得你对栈和流程控制的理解比较扎实。
缺点：还是需要一个额外的栈，空间复杂度在最坏情况下（链状树）是 O(N)，平均是 O(H)，H是树高。
解法三：Morris遍历——空间O(1)的究极解法
现在，重头戏来了。面试官如果看到你写完前两种，可能会微微一笑，然后问：“如果要求空间复杂度是 O(1)，不能用递归，也不能用栈，怎么搞？”
这时候，大部分人就懵了。这就是区分普通选手和高手的时刻。Morris 遍历就是这个问题的答案。
它的核心思想非常巧妙：利用树中大量空闲的 right 指针，来建立一个“线索”，指引我们从子树返回到父节点，从而省去栈空间。
核心思路： 用一个 cur 指针从 root 开始遍历。
如果
cur没有左子树，那么处理cur本身，然后直接去它的右子树 (cur = cur.right)。如果
cur有左子树，找到它左子树上 最右 的那个节点，我们叫它mostRight。 a. 如果mostRight的right指针是null： * 让mostRight.right = cur。这样就建立了一个从左子树回到cur的线索。 * 然后，cur移动到它的左孩子 (cur = cur.left)。 b. 如果mostRight的right指针 指向cur： * 这说明我们是通过刚才建立的线索回到了cur，代表cur的整个左子树已经处理完毕了。 * 此时，把这个线索断开，即mostRight.right = null，恢复树的结构。 * 然后，cur移动到它的右孩子 (cur = cur.right)。
整个过程，cur 指针不断在树中移动，直到最终 cur 变为 null。
用 Morris 实现三种遍历 Morris 遍历的框架是固定的，区别在于我们在哪个时间点打印值。
- 中序遍历：当中午第二次回到
cur节点时（也就是发现mostRight.right == cur，断开线索的时候），打印cur的值。因为这个时候它的左子树已经全部处理完了。对于没有左子树的节点，第一次遇到就直接打印。
public void morrisInorder(TreeNode root) {
if (root == null) {
return;
}
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) { // 有左子树
// 找到左子树的最右节点
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) { // 第一次来到cur
mostRight.right = cur;
cur = cur.left;
continue;
} else { // 第二次来到cur，通过线索回来的
mostRight.right = null; // 断开线索
}
}
// 以下是中序遍历的处理时机
System.out.print(cur.val + " ");
cur = cur.right;
}
}
- 先序遍历：在第一次来到
cur节点时就打印。对于有左子树的节点，是在建立线索（mostRight.right = cur）的时候打印。对于没有左子树的节点，是第一次遇到时就打印。
public void morrisPreorder(TreeNode root) {
if (root == null) {
return;
}
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
// 先序遍历的处理时机1
System.out.print(cur.val + " ");
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
} else {
// 先序遍历的处理时机2 (没有左子树的节点)
System.out.print(cur.val + " ");
}
cur = cur.right;
}
}
- 后序遍历：这个最复杂。时机是在第二次回到
cur节点，准备断开线索时，逆序打印cur左子树的右边界。最后，在整个流程结束后，再逆序打印整棵树的右边界。这需要一个单独的reversePrint函数。
// 后序遍历需要一个辅助函数，逆序打印链表
private void reversePrint(TreeNode from) {
TreeNode tail = reverseEdge(from);
TreeNode cur = tail;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next; // 假设TreeNode有next指针，这里仅为示意，实际是指right
}
reverseEdge(tail); // 恢复链表
}
// 实际实现
private void printEdge(TreeNode head) {
TreeNode tail = reverseList(head);
TreeNode cur = tail;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.right;
}
reverseList(tail);
}
private TreeNode reverseList(TreeNode head) {
TreeNode pre = null;
TreeNode next = null;
while (head != null) {
next = head.right;
head.right = pre;
pre = head;
head = next;
}
return pre;
}
public void morrisPostorder(TreeNode root) {
if (root == null) {
return;
}
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
// 后序遍历的关键：逆序打印cur左子树的右边界
printEdge(cur.left);
}
}
cur = cur.right;
}
// 最后单独处理整棵树的右边界
printEdge(root);
}
评价：
优点：空间复杂度为 O(1)，时间复杂度为 O(N)（看似有嵌套循环，但每条边最多被访问两次，一次建立线索，一次断开线索）。这是算法最优解，是面试中的绝对亮点。
缺点：代码实现复杂，尤其后序，难以理解，容易出错。在遍历过程中会暂时改变树的结构。
总结一下
今天我们用三种姿势把二叉树遍历给办了：
递归：代码最美，思路最清晰，但有栈溢出风险。是基础，必须掌握。
迭代（用栈）：代码相对复杂，是对递归过程的人肉模拟，考察对数据结构的运用。是进阶，也必须掌握。
Morris 遍历：代码最复杂，思路最巧妙，空间O(1)，是算法能力的体现。属于屠龙技，掌握了就是闪光点。