二叉树遍历为何如此重要：从递归到Morris的四种实现方式与LeetCode完整通关指南

当你面对一棵表达式树 (1 + 2) * 3 时，不同的遍历顺序会得到完全不同的结果：前序遍历产生前缀表达式 * + 1 2 3，中序遍历还原原始表达式 1 + 2 * 3（需要括号），后序遍历产生后缀表达式 1 2 + 3 *——这正是逆波兰表示法，可以直接用于栈式计算器。这就是二叉树遍历的核心价值：遍历顺序决定了数据的处理方式。

二叉树作为最基础的树形数据结构，每个节点最多有两个子节点。这种简洁的结构却能表达层次关系、递归逻辑和决策过程。而遍历——按照某种规则访问每个节点恰好一次——是所有树操作的基石。无论是查找、插入、删除，还是序列化、反序列化，本质上都是遍历的变种。

为什么只有四种基本遍历

给定一棵二叉树，对于任意节点，有三个访问时机：进入节点时、遍历完左子树后、遍历完右子树后。这三个时机分别对应前序、中序、后序遍历。如果用 D 表示访问根节点，L 表示遍历左子树，R 表示遍历右子树，那么：

前序遍历 (DLR)：先访问根，再左子树，最后右子树
中序遍历 (LDR)：先左子树，再访问根，最后右子树
后序遍历 (LRD)：先左子树，再右子树，最后访问根

层序遍历则是另一种维度——横向扫描。它从根节点开始，逐层从左到右访问节点，本质上是广度优先搜索 (BFS)。

graph TB
    subgraph 示例二叉树
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
    end

对于上面这棵树，四种遍历的结果分别是：

前序：1, 2, 4, 5, 3
中序：4, 2, 5, 1, 3
后序：4, 5, 2, 3, 1
层序：1, 2, 3, 4, 5

这四种遍历各有其独特应用：

遍历方式	典型应用
前序遍历	复制二叉树、序列化二叉树、前缀表达式
中序遍历	BST有序输出、表达式树求值（中缀）
后序遍历	删除二叉树、计算目录大小、后缀表达式
层序遍历	按层处理、右视图、最大宽度

递归实现：最直观的表达

递归实现与遍历定义直接对应，代码几乎可以逐字翻译。以中序遍历为例：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);   // L
    result.add(node.val);          // D
    inorder(node.right, result);   // R
}

前序和后序只需调整 result.add(node.val) 的位置。递归的优雅在于它完全反映了问题的递归定义：一棵二叉树的遍历 = 根节点的访问 + 左子树遍历 + 右子树遍历。

但递归的代价是空间复杂度 O(h)，其中 h 是树高。对于平衡树这是 O(log n)，对于退化为链表的树则是 O(n)。调用栈存储了从根到当前节点的完整路径，这正是递归"记住"如何返回的机制。

迭代实现：用显式栈模拟调用栈

递归的本质是编译器帮我们维护了一个隐式栈。迭代实现则显式地管理这个栈。以中序遍历为例，核心思想是：一直向左走到底，途中节点入栈；到底后弹出栈顶访问，然后转向右子树。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        // 一直向左走
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // 弹出栈顶访问
        curr = stack.pop();
        result.add(curr.val);
        // 转向右子树
        curr = curr.right;
    }
    return result;
}

前序遍历的迭代实现稍有不同——访问时机在入栈时：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    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;
}

后序遍历的迭代实现是最复杂的，因为需要"左-右-根"的顺序，而我们无法预先知道右子树是否处理完毕。常用技巧是反向后序遍历：先得到"根-右-左"的序列，再反转得到"左-右-根"。

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);    // 头插法实现反转
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return result;
}

Morris遍历：O(1)空间的魔法

1979年，Joseph M. Morris 在论文《Traversing Binary Trees Simply and Cheaply》中提出了一种革命性的遍历方法。其核心思想来自线索二叉树 (Threaded Binary Tree)——利用叶子节点的空指针，临时指向中序遍历的前驱或后继节点。

Morris遍历的关键步骤：

如果当前节点没有左子树，访问它并转向右子树
如果当前节点有左子树，找到其左子树的最右节点（中序前驱）
如果前驱的右指针为空，将其指向当前节点（建立线索），转向左子树
如果前驱的右指针指向当前节点（线索已存在），断开线索，访问当前节点，转向右子树

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;
    
    while (curr != null) {
        if (curr.left == null) {
            // 没有左子树，直接访问
            result.add(curr.val);
            curr = curr.right;
        } else {
            // 找到中序前驱
            TreeNode predecessor = curr.left;
            while (predecessor.right != null && predecessor.right != curr) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                // 建立线索
                predecessor.right = curr;
                curr = curr.left;
            } else {
                // 线索已存在，断开并访问
                predecessor.right = null;
                result.add(curr.val);
                curr = curr.right;
            }
        }
    }
    return result;
}

Morris遍历的时间复杂度仍是 O(n)，因为每条边最多被访问三次（向下、通过线索向上、断开线索）。但空间复杂度降到了 O(1)，这在内存受限的嵌入式系统或处理超大规模树时非常有价值。

graph TB
    subgraph Morris遍历建立线索的过程
        direction LR
        A1((1)) -.->|建立线索| B1((2))
        B1((2)) --> C1((4))
        B1 --> D1((5))
        A1 --> E1((3))
        C1 -.->|建立线索| A1
        D1 -.->|建立线索| A1
    end

上图展示了Morris遍历中如何利用空指针建立临时线索（虚线），使得遍历完成后可以回到父节点，从而避免使用栈。

LeetCode题目分类详解

遍历基础题 (LeetCode 94, 144, 145)

这三道题分别要求实现中序、前序、后序遍历。上面已经给出了完整代码。面试时一个常见追问是：能否用统一的方式实现三种遍历？

答案是使用"标记法"——在每个节点入栈时附带一个标记，表示是否已访问过：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<Object[]> stack = new ArrayDeque<>();
    
    if (root != null) stack.push(new Object[]{root, false});
    
    while (!stack.isEmpty()) {
        Object[] item = stack.pop();
        TreeNode node = (TreeNode) item[0];
        boolean visited = (boolean) item[1];
        
        if (visited) {
            result.add(node.val);
        } else {
            // 中序：左 -> 根 -> 右，入栈顺序相反
            if (node.right != null) stack.push(new Object[]{node.right, false});
            stack.push(new Object[]{node, true});
            if (node.left != null) stack.push(new Object[]{node.left, false});
        }
    }
    return result;
}

只需调整入栈顺序即可切换遍历方式。

层序遍历 (LeetCode 102, 103, 107)

层序遍历使用队列实现 BFS：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

LeetCode 103 锯齿形层序遍历只需在偶数层反转结果：

if (result.size() % 2 == 1) {
    Collections.reverse(level);
}

二叉树构造 (LeetCode 105, 106, 108, 109)

从前序+中序或后序+中序构造二叉树是经典的分治问题。核心原理是：

前序遍历的第一个元素是根节点
中序遍历中根节点将序列分为左右子树
递归处理左右子树

// LeetCode 105: 从前序与中序遍历序列构造二叉树
private int preIndex = 0;
private Map<Integer, Integer> inorderMap = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return build(preorder, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, int inStart, int inEnd) {
    if (inStart > inEnd) return null;
    
    int rootVal = preorder[preIndex++];
    TreeNode root = new TreeNode(rootVal);
    
    int inIndex = inorderMap.get(rootVal);
    root.left = build(preorder, inStart, inIndex - 1);
    root.right = build(preorder, inIndex + 1, inEnd);
    
    return root;
}

LeetCode 108 将有序数组转为平衡 BST，关键是选择中间元素作为根：

public TreeNode sortedArrayToBST(int[] nums) {
    return buildBST(nums, 0, nums.length - 1);
}

private TreeNode buildBST(int[] nums, int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = buildBST(nums, left, mid - 1);
    root.right = buildBST(nums, mid + 1, right);
    return root;
}

二叉树修改 (LeetCode 226, 114)

LeetCode 226 翻转二叉树是一道经典的递归题：

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

LeetCode 114 二叉树展开为链表要求原地修改：

public void flatten(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left != null) {
            TreeNode predecessor = curr.left;
            while (predecessor.right != null) {
                predecessor = predecessor.right;
            }
            predecessor.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
}

路径问题 (LeetCode 112, 113, 124, 257)

LeetCode 112 路径总和检查是否存在根到叶路径等于目标和：

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val) 
        || hasPathSum(root.right, targetSum - root.val);
}

LeetCode 124 二叉树最大路径和是一道困难题，关键是理解"路径"的定义：

private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
}

private int maxGain(TreeNode node) {
    if (node == null) return 0;
    
    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);
    
    // 以当前节点为根的路径和
    int newPathSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, newPathSum);
    
    // 返回以当前节点为端点的最大路径和
    return node.val + Math.max(leftGain, rightGain);
}

属性判断 (LeetCode 101, 104, 110)

LeetCode 101 对称二叉树需要同时递归两棵子树：

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

private boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return t1.val == t2.val 
        && isMirror(t1.left, t2.right) 
        && isMirror(t1.right, t2.left);
}

LeetCode 110 平衡二叉树需要在计算高度的同时判断平衡：

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

private int height(TreeNode node) {
    if (node == null) return 0;
    
    int leftHeight = height(node.left);
    if (leftHeight == -1) return -1;
    
    int rightHeight = height(node.right);
    if (rightHeight == -1) return -1;
    
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    
    return Math.max(leftHeight, rightHeight) + 1;
}

最近公共祖先 (LeetCode 235, 236)

LeetCode 236 二叉树的最近公共祖先是高频面试题：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

对于 BST (LeetCode 235)，可以利用 BST 的性质简化：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
}

视图问题 (LeetCode 199)

LeetCode 199 二叉树右视图返回从右侧能看到的所有节点：

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (i == levelSize - 1) {
                result.add(node.val);
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return result;
}

解题模式总结

解决二叉树问题，本质上就是选择合适的遍历方式：

需要先处理子节点再处理父节点 → 后序遍历（如计算树高、求和、LCA）
需要先处理父节点再处理子节点 → 前序遍历（如复制树、路径问题）
需要按层级处理 → 层序遍历（如右视图、按层统计）
BST 需要有序访问 → 中序遍历

递归是最自然的思路，但迭代和 Morris 遍历展示了如何用显式数据结构替代隐式调用栈。理解这三种实现方式的等价性，是掌握树形数据结构的关键一步。

参考文献

Morris, Joseph H. “Traversing binary trees simply and cheaply.” Information Processing Letters 9.5 (1979): 197-200.
Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, 1968.
Perlis, Alan Jay, and C. Thornton. “Symbol manipulation by threaded lists.” Communications of the ACM 3.4 (1960): 195-204.
GeeksforGeeks. “Tree Traversal Techniques.” https://www.geeksforgeeks.org/dsa/tree-traversals-inorder-preorder-and-postorder/
Wikipedia. “Threaded binary tree.” https://en.wikipedia.org/wiki/Threaded_binary_tree
LeetCode. “Binary Tree Problem List.” https://leetcode.com/problem-list/binary-tree/

为什么只有四种基本遍历#

递归实现：最直观的表达#

迭代实现：用显式栈模拟调用栈#

Morris遍历：O(1)空间的魔法#

LeetCode题目分类详解#

遍历基础题 (LeetCode 94, 144, 145)#

层序遍历 (LeetCode 102, 103, 107)#

二叉树构造 (LeetCode 105, 106, 108, 109)#

二叉树修改 (LeetCode 226, 114)#

路径问题 (LeetCode 112, 113, 124, 257)#

属性判断 (LeetCode 101, 104, 110)#

最近公共祖先 (LeetCode 235, 236)#

视图问题 (LeetCode 199)#

解题模式总结#

参考文献#

更多精彩内容

树形动态规划：为什么一棵树的答案要从叶子开始算

深度优先与广度优先搜索:从栈与队列的选择到最短路径的博弈

回溯算法:从决策树到剪枝优化的完整LeetCode通关指南

动态规划算法入门：从暴力递归到状态转移的完整思维指南

股票买卖问题为何能用一套代码解决所有变体从状态机DP到贪心的统一框架