树的遍历
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
}
二叉树 DFS 中根据访问根节点、左子节点、右子节点的不同顺序，可以分为：
- 前序遍历，Pre-order (NLR)
- 中序遍历，In-order (LNR)
- 后序遍历，Post-order (LRN)
递归遍历
void traversal(TreeNode root) {
if (root == null) return;
// System.out.println(root.val); // 前序遍历访问节点
traversal(root.left);
// System.out.println(root.val); // 中序遍历访问节点
traversal(root.right);
// System.out.println(root.val); // 后序遍历访问节点
}
递归遍历的方式代码简洁明了。
迭代遍历
迭代遍历通常需要栈来辅助。
前序遍历：
void traversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// 访问
System.out.println(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
访问当前节点后依次压入右子节点和左子节点即可，因为左子节点比右子节点需要先弹出栈（先被访问），所以后压入。
中序遍历：
void traversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
// 访问
System.out.println(cur.val);
cur = cur.right;
}
}
一样是模拟出递归的隐式栈调用，对于当前节点一路压入左子节点，访问后将当前节点置为弹出节点的右子节点。
后序遍历：
void traversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode pre = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
if (!stack.isEmpty()) {
cur = stack.pop();
// 右节点都访问过（或者为空不需要访问）则访问 cur 这个根节点
if (cur.right == null || cur.right == pre) {
// 访问
System.out.println(cur.val);
pre = cur;
cur = null; // 不需要再访问左子节点了
} else { // push back 待访问的根节点 准备访问右节点
stack.push(cur);
cur = cur.right;
}
}
}
}
后序遍历稍微复杂一点，经过根节点的时候不会去访问它，会先访问它的右子节点，所以将根节点留在栈中不弹出。当前节点是叶子节点，或者当访问完右子节点之后，就需要访问根节点了。通过记录上一次访问的节点和当前节点的右子节点的关系就可以进行判断。
算法复杂度
对于时间复杂度，最理想的情况就 O(n)，即每个节点只访问一次，无需再优化。
对于空间复杂度，迭代是显式的栈调用，递归存在隐式栈调用，空间复杂度取决于树高度。平均情况下为 O(logn)，最坏情况下树呈链状，为 O(n)。
时间复杂度已经无法优化，而空间复杂度是存在优化的空间的。
Morris 遍历
不使用额外空间遍历的难点在于遍历到子节点时应该如何回到父节点，Morris 遍历使用到了线索二叉树的概念，利用树的大量空闲指针，实现空间开销的缩减。
线索二叉树是指为二叉树添加了指向前驱和后继的指针的二叉树。
- 所有原本为空的左指针改为指向该节点的中序序列中的前驱。
- 所有原本为空的右指针改为指向该节点在中序序列中的后继。
实际在 Morris 遍历中并不需要为每个节点都额外分配指针指向其前驱和后继节点，只需要利用叶子节点中的闲置的右指针指向后继节点就可以了。对于当前节点，从其左节点沿着右指针一直往右走，直到走到叶子节点为止，这个叶子节点就是当前节点在中序遍历中的前驱节点。
中序遍历
以中序遍历为例：
如果 cur 没有左子节点，那么就访问 cur，再继续访问 cur 的右子节点。
如果 cur 有左子节点，则找到 cur 的前驱节点 pre，根据前驱节点的右子节点是否为空来进行操作。
- 如果 pre 的右子节点为空，则将 pre 的右指针指向 cur，再去访问 cur 的左子节点。
- 如果 pre 的右子节点不为空，说明已经遍历完 cur 的左子树，此时 pre 的右子节点指向的就是 cur。此时可以断开 pre 与 cur 的链接，访问 cur，再继续访问 cur 的右子节点。
- 重复上述操作，直至访问完整棵树。
void traversal(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pre = cur.left;
// 找前驱节点
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) { // 左子树未访问完
// 前驱节点右指针指向当前节点
pre.right = cur;
// 继续访问左子树
cur = cur.left;
} else { // 左子树已经访问完毕
pre.right = null;
// 访问节点
System.out.println(cur.val);
cur = cur.right;
}
} else { // 没有左子节点 准备访问右子节点
// 访问节点
System.out.println(cur.val);
cur = cur.right;
}
}
}
找前驱节点的循环中条件 pre.right != cur 是为了避免成环后找到错误的 pre。例如遍历中会将 A 闲置的右指针指向 B（A 是 B 的前驱节点），访问 A 后通过 cur = cur.right 又会回到 B，此时 B 再次找到前驱 A 的时候，就应该知道 B 的左子树已经访问完毕，该访问 B 的右子节点了。否则会普通的把 B 当作 A 的右子节点，并继续一直向右走找到 E，把 E 当作 B 的前驱。
代码的实现上面可以继续简化，两个访问点可以理解为同一种情况，就是左子树已经访问完毕。可以在将前驱节点的右指针指向当前节点，并将当前节点（旧 cur）更新为当前节点的左子节点（新 cur）后，通过提前赋值好的指针，将旧的当前节点断开和左子树的链接，这样就不会成环了。
void traversal(TreeNode root) {
TreeNode curr = root;
TreeNode pre;
while (curr != null) {
if (curr.left == null) {
// 访问节点
System.out.println(cur.val);
curr = curr.right;
} else {
pre = curr.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = curr;
TreeNode temp = curr;
curr = curr.left;
// 断开和左子树的联系
temp.left = null;
}
}
}
前序遍历
前序遍历与中序遍历的步骤基本相同，只在于访问的时机略有不同。
由于前序遍历是按照 NLR 的顺序进行访问，所以对于 cur 来说，左子节点为空时就访问自己，并准备访问右子节点。因为访问当前节点总在访问当前节点的左子树之前，所以通过 pre 回到 cur 的时候，直接准备访问 cur 的右子节点即可。
void traversal(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
// 访问节点
System.out.println(cur.val);
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
cur = cur.right;
}
} else {
// 访问节点
System.out.println(cur.val);
cur = cur.right;
}
}
}
后序遍历
后序遍历需要注意输出路径的反转。
void traversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
// 倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点
reverse(cur.left, list);
cur = cur.right;
}
} else {
cur = cur.right;
}
}
reverse(root, list);
System.out.println(list);
}
void reverse(TreeNode node, List<Integer> list) {
int count = 0;
while (node != null) {
list.add(node.val);
node = node.right;
count++;
}
int left = list.size() - count;
int right = list.size() - 1;
while (left < right) {
int temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
left++;
right--;
}
}
上面虽然使用 list 存储访问结果，并在 reverse 方法中做了反转了，但是完全可以做到实时按序输出。
如果不需要实时按序输出，也可以采用反转单词串的方式进行访问。反转一个单词串的一种思想就是两次反转，第一次对整个字符串反转，再逐词反转就完成了反转单词串。
应用到二叉树，可以用 NRL 的顺序进行 Morris 遍历，最后全体反转一次就变成了 LRN。
void travel(TreeNode root) {
List<Integer> list = new LinkedList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.right == null) {
list.add(cur.val);
cur = cur.left;
} else {
TreeNode pre = cur.right;
while (pre.left != null && pre.left != cur) {
pre = pre.left;
}
if (pre.left == cur) {
pre.left = null;
cur = cur.left;
} else {
list.add(cur.val);
pre.left = cur;
cur = cur.right;
}
}
}
Collections.reverse(list);
System.out.println(list);
}
树的遍历或者说按照某种定义的方式进行遍历的本质应该是对数据结构的有序访问，如果不按照访问顺序，只是最后用数据结构恢复了顺序，遍历的过程就失去了「意义」。
比如上面的遍历其实进行的就是一种异构的前序遍历（NRL，而非 NLR ），这种异构访问可以当作是「反转单词串」中的第一次反转，最后的反转就是第二次反转，这是一种 trick。
当然并不是说「trick」不好，对于反转单词串来说就是一种比较优雅的算法实现，只是这里更加强调「遍历」。
算法复杂度
对于空间复杂度，只使用了空闲的指针，没有使用额外的空间，所以是 O(1)。
对于时间复杂度，由于存在找前驱节点的循环，直觉上看和树高相关，可能是 O(nlgn)，但是实际上每一条边只会走两次，第一次是为了找前驱节点，第二次是为了到达某个节点，所以复杂度是 O(n)。