一、啥是二叉树遍历
咱先聊聊二叉树遍历是个啥。简单来说，二叉树就是一种树状的数据结构，每个节点最多有俩孩子，分别叫左孩子和右孩子。遍历二叉树呢，就是按照一定规则把树里的每个节点都访问一遍。常见的遍历方式有前序、中序和后序遍历。
前序遍历就是先访问根节点，再遍历左子树，最后遍历右子树；中序遍历是先遍历左子树，再访问根节点，最后遍历右子树；后序遍历则是先遍历左子树，再遍历右子树，最后访问根节点。
比如说有这么一个简单的二叉树，根节点是 1，左孩子是 2，右孩子是 3。前序遍历的结果就是 1、2、3；中序遍历是 2、1、3；后序遍历是 2、3、1。
// Java 代码示例，定义一个简单的二叉树节点类
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// 前序遍历方法
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历方法
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历方法
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
二、传统遍历方法的问题
传统的二叉树遍历方法，像递归和使用栈的迭代方法，都有一个问题，就是需要额外的空间。递归方法会用到系统栈，栈的深度和树的高度有关，要是树的高度很大，栈空间就会占用很多。使用栈的迭代方法也需要一个栈来辅助遍历，同样会占用额外的空间。
比如说，有一个深度为 100 的二叉树，递归遍历的时候，系统栈可能会占用 100 层的空间，这对于内存来说是个不小的负担。要是树的节点很多，空间消耗就会更大。
// 递归前序遍历示例
public void recursivePreOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
recursivePreOrder(root.left);
recursivePreOrder(root.right);
}
// 使用栈的迭代前序遍历示例
import java.util.Stack;
public void iterativePreOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
三、Morris 遍历算法登场
Morris 遍历算法就是为了解决传统遍历方法空间复杂度高的问题而出现的。它的核心思想是利用二叉树中那些空闲的指针，把它们用来临时记录遍历的路径，这样就不需要额外的栈空间了，从而实现了 O(1) 的空间复杂度。
具体来说，Morris 遍历会先找到当前节点左子树的最右节点，然后把这个最右节点的右指针指向当前节点，这样就可以在遍历完左子树后回到当前节点。
四、Morris 遍历算法详细步骤
1. 初始化
从根节点开始，设置当前节点为根节点。
2. 遍历过程
- 如果当前节点的左子树为空，就访问当前节点，然后把当前节点移动到右子节点。
- 如果当前节点的左子树不为空，找到左子树的最右节点。
- 如果最右节点的右指针为空，就把它的右指针指向当前节点，然后把当前节点移动到左子节点。
- 如果最右节点的右指针已经指向当前节点，说明左子树已经遍历完了，把这个指针恢复为空，访问当前节点，然后把当前节点移动到右子节点。
3. 结束条件
当当前节点为空时，遍历结束。
// Java 实现 Morris 中序遍历
public void morrisInOrder(TreeNode root) {
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// 如果左子树为空，直接访问当前节点
System.out.print(current.val + " ");
current = current.right;
} else {
// 找到左子树的最右节点
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 如果最右节点的右指针为空，将其指向当前节点
predecessor.right = current;
current = current.left;
} else {
// 如果最右节点的右指针已经指向当前节点，恢复指针并访问当前节点
predecessor.right = null;
System.out.print(current.val + " ");
current = current.right;
}
}
}
}
五、Morris 遍历算法示例分析
咱还是用之前那个简单的二叉树，根节点是 1，左孩子是 2，右孩子是 3。
1. 初始状态
当前节点是 1，左子树不为空，找到左子树（节点 2）的最右节点，也就是 2 本身。因为 2 的右指针为空，把 2 的右指针指向 1，然后当前节点移动到 2。
2. 遍历左子树
当前节点是 2，左子树为空，访问 2，然后当前节点移动到右子节点，也就是 1。
3. 回到根节点
此时 2 的右指针指向 1，说明左子树已经遍历完了，把 2 的右指针恢复为空，访问 1，然后当前节点移动到 3。
4. 遍历右子树
当前节点是 3，左子树为空，访问 3，然后当前节点移动到右子节点，此时右子节点为空，遍历结束。
最终的遍历结果是 2、1、3，和中序遍历的结果一致。
六、应用场景
Morris 遍历算法在内存资源有限的情况下非常有用。比如说在嵌入式系统中，内存空间比较小，传统的遍历方法可能会导致内存不足，而 Morris 遍历算法只需要常数级的额外空间，就可以完成二叉树的遍历。
还有在处理大规模数据的二叉树时，使用 Morris 遍历可以节省大量的内存空间，提高程序的性能。
七、技术优缺点
优点
- 空间复杂度低：只需要常数级的额外空间，这是 Morris 遍历算法最大的优点。
- 不依赖栈：不需要使用额外的栈来辅助遍历，避免了栈溢出的风险。
缺点
- 修改树结构：在遍历过程中会临时修改树的指针，虽然最后会恢复，但对于一些不允许修改树结构的应用场景不太适用。
- 复杂度较高：代码实现相对复杂，理解起来也有一定难度。
八、注意事项
- 在使用 Morris 遍历算法时，要注意恢复树的指针，避免对树的结构造成永久性的破坏。
- 对于一些对树结构有严格要求的场景，要谨慎使用 Morris 遍历算法。
九、文章总结
Morris 遍历算法是一种非常巧妙的二叉树遍历算法，它通过利用二叉树中空闲的指针，实现了 O(1) 的空间复杂度。虽然它有一些缺点，比如会临时修改树的结构和代码实现相对复杂，但在内存资源有限的场景下，它的优势非常明显。开发者可以根据具体的应用场景来选择是否使用 Morris 遍历算法。
评论