二叉树遍历与链表相交问题
整理二叉树递归与非递归遍历、递归序，以及环形链表和相交链表的判断方法。
1. 二叉树的前中后序遍历
二叉树的遍历是指按照某种顺序访问树中的所有节点。最常见的三种遍历方式是前序、中序和后序遍历。
1.1 递归遍历
递归是实现二叉树遍历最自然和直观的方式。其本质是利用了函数调用栈。
1.1.1 理解递归序
要理解递归遍历，首先要理解“递归序”。当我们递归地处理一个节点（例如 f(root)）时，实际上每个节点都会在递归过程中被“经过”三次：
- 第一次到达该节点时（在
f(root.left)调用之前）。 - 从左子树返回，第二次到达该节点时（在
f(root.left)之后，f(root.right)之前）。 - 从右子树返回，第三次到达该节点时（在
f(root.right)之后）。
前序、中序、后序遍历的本质，就是在递归序的不同时机去处理（例如打印）节点：
- 前序：在第一次到达节点时处理。
- 中序：在第二次到达节点时处理。
- 后序：在第三次到达节点时处理。
1.1.2 前序遍历
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。这对应了在递归序中第一次遇到节点时就进行处理。
java
public void pre(Node root) {
if (root == null) return;
System.out.println(root.val);
pre(root.left);
pre(root.right);
}
1.1.3 中序遍历
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。这对应了在递归序中第二次遇到节点（即从左子树返回）时进行处理。
java
public void mid(Node root) {
if (root == null) return;
mid(root.left);
System.out.println(root.val);
mid(root.right);
}1.1.4 后序遍历
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。这对应了在递归序中第三次遇到节点（即从右子树也返回）时进行处理。
java
public void pos(Node root) {
if (root == null) return;
pos(root.left);
pos(root.right);
System.out.println(root.val);
}1.2 非递归遍历
非递归遍历（或称迭代遍历）需要我们自己管理一个栈，以模拟递归的行为。
1.2.1 前序遍历
非递归前序（根左右）的思路是利用栈的“后进先出”特性：
- 将根节点压入栈。
- 循环执行直到栈为空：
- 弹出栈顶元素
pop并打印。 - 先将
pop的右孩子压入栈（如果存在）。 - 后将
pop的左孩子压入栈（如果存在）。
- 弹出栈顶元素
- 这样，出栈的顺序就自然地变成了“根-左-右”。
java
public void pre(Node root) {
if (root == null) return;
Stack<Node> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
Node pop = s.pop();
System.out.println(pop.val);
if (pop.right != null) {
s.push(pop.right);
}
if (pop.left != null) {
s.push(pop.left);
}
}
}1.2.2 中序遍历
非递归中序（左根右）的实现相对复杂：
- 使用一个
cur指针指向当前节点，初始为root。 - 外层循环条件为
cur != null或!s.isEmpty()。 - 内层循环：当
cur != null时，不断将cur压栈，并让cur移动到其左孩子（cur = cur.left）。这实现了对“左”的一路到底。 - 当内层循环结束（
cur为null），说明最左的节点已经入栈。 - 从栈中弹出一个元素
pop并打印（处理“根”）。 - 将
cur指向pop的右孩子（cur = pop.right），准备处理“右”子树。
java
public void mid(Node root) {
if (root == null) return;
Node cur = root;
Stack<Node> s = new Stack<>();
while (cur != null || !s.isEmpty()) {
while (cur != null) {
s.push(cur);
cur = cur.left;
}
Node pop = s.pop();
System.out.println(pop.val);
cur = pop.right;
}
}
1.2.3 后序遍历
非递归后序（左右根）的实现有一个巧妙的思路，它利用了两个栈：
- 后序是“左右根”。
- 如果我们调整前序（根左右）的压栈顺序，变为先压左、再压右，那么出栈顺序就会变成“根右左”。
- “根右左”这个顺序，恰好是“左右根”的完全逆序。
- 因此，我们可以：
- 使用
s1实现“根右左”的遍历。 - 将
s1弹出的元素，不打印，而是压入s2。 - 当
s1为空时，s2中就存储了“左右根”的顺序。 - 最后，依次弹出
s2的所有元素并打印。
- 使用
java
public void pos(Node root) {
if (root == null) return;
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
Node pop = s1.pop();
s2.push(pop);
if (pop.left != null) {
s1.push(pop.left);
}
if (pop.right != null) {
s1.push(pop.right);
}
}
while (!s2.isEmpty()) {
System.out.println(s2.pop().val);
}
}
2. 寻找两个链表的相交节点
这是一个复杂但经典的链表问题。给定两个单链表，它们可能无环，也可能有环。如果它们相交，要求返回第一个相交节点。要求时间复杂度 $O(N)$，额外空间复杂度 $O(1)$。
2.1 核心思路：分类讨论
解决这个问题的关键是对所有可能性进行分类。我们首先需要一个辅助函数来判断链表是否有环，并返回第一个入环节点。
根据两个链表的入环节点（loop1, loop2），我们可以分为三大类情况：
loop1 == null且loop2 == null：两个链表都无环。loop1 != null且loop2 != null：两个链表都有环。- 一个有环一个无环：这种情况，两个链表绝对不可能相交。
2.2 辅助函数：判断链表是否有环
我们使用“快慢指针”法（Floyd's Tortoise and Hare）来检测环，并找到入环点：
- 设置
slow指针（一次走一步）和fast指针（一次走两步）。 - 如果
fast走到了null（或fast.next == null），说明无环，返回null。 - 如果
slow和fast相遇，说明有环。 - 重要结论：相遇后，将
fast指针移回head，slow保持不动。然后两者都变成一次走一步。它们下一次相遇的节点，就是第一个入环节点。
java
public Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node slow = head.next;
Node fast = head.next.next;
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
2.3 场景一：两个链表均无环
这是最简单的情况：
- 如果两个无环链表相交，那么它们从相交点开始，后续的节点必定完全共享，因此它们的最后一个节点一定是同一个节点。
- 遍历两个链表，得到它们的长度
len1、len2和尾节点tail1、tail2。 - 如果
tail1 != tail2，它们必不相交，返回null。 - 如果相交，计算长度差
diff。让较长链表的指针先走diff步。 - 然后两个指针一起走，它们相遇的第一个节点就是相交节点。
java
public Node noLoop(Node head1, Node head2) {
int len1 = 1;
int len2 = 1;
Node cur1 = head1;
Node cur2 = head2;
while (cur1.next != null) {
len1++;
cur1 = cur1.next;
}
while (cur2.next != null) {
len2++;
cur2 = cur2.next;
}
if (cur1 != cur2) return null;
int diff = len1 - len2;
cur1 = diff > 0 ? head1 : head2;
cur2 = diff > 0 ? head2 : head1;
for (int i = 0; i < Math.abs(diff); i++) {
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
2.4 场景二：一个有环一个无环
如前所述，这种情况不可能相交。一个无环链表的终点是 null，而一个有环链表永远在环里。它们没有公共节点。
2.5 场景三：两个链表均有环
这是最复杂的情况，又可以细分为两种：
loop1 == loop2：- 这意味着两个链表在入环前就相交了，共用同一个入环点。
- 问题退化为“场景一”。我们可以把
loop1视为两个链表的“伪尾节点”，用noLoop的逻辑来找环外的相交点。
loop1 != loop2：- 这不代表它们不相交，它们可能共享了同一个环，只是入环点不同。
- 检测方法：让一个指针
cur从loop1.next出发，在环上走一圈。 - 如果在回到
loop1之前遇到了loop2，说明它们在同一个环上，相交。此时返回loop1或loop2均可（它们都是相交点）。 - 如果
cur走回了loop1都没有遇到loop2，说明它们是两个独立的环，不相交，返回null。
java
public Node doubleLoop(Node head1, Node head2, Node loop1, Node loop2) {
if (loop1 == loop2) {
int n = 0;
Node cur1 = head1;
Node cur2 = head2;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = n > 0 ? head2 : head1;
for (int i = 0; i < Math.abs(n); i++) {
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
Node cur = loop1.next;
while (cur != loop1) {
if (cur == loop2) {
return loop1;
}
cur = cur.next;
}
return null;
}
2.7 完整实现
最后，我们将所有逻辑组合在主函数中：
java
public Node findFirstIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) return null;
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) return noLoop(head1, head2);
if (loop1 != null && loop2 != null) return doubleLoop(head1, head2, loop1, loop2);
return null;
}