深入理解二叉树遍历：递归与栈的双重视角

admin管理员组

文章数量:1437470

深入理解二叉树遍历：递归与栈的双重视角

二叉树的遍历

虽然用递归的方法遍历二叉树实现起来更简单，但是要想深入理解二叉树的遍历，我们还必须要掌握用栈遍历二叉树，递归其实就是利用了系统栈去遍历。特此记录一下如何用双重视角去看待二叉树的遍历，加深一下理解。

前序遍历

我们从前序遍历入手，搞懂了一个，其它的也就容易了。

使用递归的方法遍历的话很简单，代码如下：

代码语言：java复制

public void preorderTraversal(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    
    // 访问根节点
    result.add(root.val);
    
    // 递归遍历左子树
    preorderTraversal(root.left, result);
    
    // 递归遍历右子树
    preorderTraversal(root.right, result);
}

它利用了系统中线程的栈空间，先访问当前节点，再调用自身方法递归地去对左子节点进行前序遍历，这在线程栈空间中会新增加一个方法。线程也会优先去处理在线程栈上新增的方法。如下图所示：

这里发生的事情是：

1. 系统为每次方法调用维护一个执行上下文，包含局部变量和返回地址
2. 当执行到preorder(root.left)时，当前方法的执行被暂停，其状态被保存在系统栈中
3. 系统转而执行左子树的遍历，完成后会自动返回到保存的执行点
4. 继续执行preorder(root.right)

关键点是：系统栈自动保存了"接下来要做什么"的信息。每个节点被处理时，系统知道处理完左子树后还需要回来处理右子树。

而使用栈的话，我们只需要按照递归遍历的方式自己创建一个栈模拟着线程栈的方法去遍历就行。代码如下：

代码语言：java复制

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        // 先右后左入栈，这样出栈时会先处理左子节点
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    
    return result;
}

这里的关键区别是：

1. 我们只能用栈存储节点本身，而不能存储"执行到哪一步"的完整上下文
2. 栈顶元素是下一个要处理的节点，而不是一个带有执行状态的方法调用
3. 由于栈的后进先出特性，为了先处理左子节点，必须先将右子节点入栈，再将左子节点入栈

系统线程栈和手动实现栈的对应关系：

• 系统线程栈的一个栈帧的运行（不包括递归调用产生的跳转）等同于手动实现栈的三件事： 1.访问当前节点 2.入栈右子节点 3.入栈左子节点
• 系统线程栈新增了一个栈帧等同于手动实现栈的：出栈一个节点作为当前节点

中序遍历

递归代码如下：

代码语言：java复制

public void inorderTraversal(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    
    // 递归遍历左子树
    inorderTraversal(root.left, result);
    
    // 访问根节点
    result.add(root.val);
    
    // 递归遍历右子树
    inorderTraversal(root.right, result);
}

系统线程栈中一个栈帧的执行过程（不包括递归调用产生的跳转）等同于手动实现栈中的三个操作：

1. 递归访问左子树
2. 访问当前节点
3. 递归访问右子树

手动实现栈代码如下：

代码语言：java复制

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 将所有左子节点入栈
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 处理栈顶节点
        current = stack.pop();
        result.add(current.val);
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

核心思路是先将当前节点及其所有左子节点入栈，然后访问节点值，再处理右子树

无法用简单的"入栈-出栈-访问"模式表达，需要维护一个current指针跟踪当前处理节点

关键步骤：

1. 将当前节点及其所有左子节点入栈
2. 弹出栈顶节点并访问
3. 将当前节点切换到右子节点，重复步骤1

后续遍历

递归代码如下：

代码语言：java复制

public void postorderTraversal(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    
    // 递归遍历左子树
    postorderTraversal(root.left, result);
    
    // 递归遍历右子树
    postorderTraversal(root.right, result);
    
    // 访问根节点
    result.add(root.val);
}

系统线程栈中一个栈帧的执行过程等同于手动实现栈中的三个操作：

1. 递归访问左子树
2. 递归访问右子树
3. 访问当前节点

手动实现栈代码如下：

代码语言：java复制

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    
    stack1.push(root);
    
    // 先将节点按 根-右-左 的顺序放入栈2
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    
    // 从栈2中弹出的顺序就是 左-右-根
    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }
    
    return result;
}

双栈法

系统线程栈中一个栈帧的执行等同于：

1. 将当前节点压入第二个栈（结果栈）
2. 将左子节点压入第一个栈（处理栈）
3. 将右子节点压入第一个栈（处理栈）

注意：入栈顺序是"左-右"，这样处理顺序变成"右-左"，最终从结果栈弹出时顺序为"左-右-根"

单栈法

1. 需要额外记录上次访问的节点
2. 核心思路是判断右子树是否已访问，决定是访问节点还是处理右子树
3. 由于逻辑较复杂，难以用简单的等价操作表述

总结

读者可以根据前序遍历的思路自行去理解中序遍历和后序遍历。重点就是理解系统的线程栈是怎么运作的，以及手动实现的栈是如何保存节点的。搞清楚了这两点，对二叉树的遍历的理解就会更上一层了。

本文标签： 深入理解二叉树遍历递归与栈的双重视角