首页
/ 前端算法面试难点解析：二叉树遍历的四种经典方式

前端算法面试难点解析：二叉树遍历的四种经典方式

2026-02-04 04:51:30作者：晏闻田Solitary
frontend-hard-mode-interview
《前端内参》，有关于JavaScript、编程范式、设计模式、软件开发的艺术等大前端范畴内的知识分享，旨在帮助前端工程师们夯实技术基础以通过一线互联网企业技术面试。
项目地址：https://gitcode.com/gh_mirrors/fr/frontend-hard-mode-interview

前言：为什么二叉树遍历是前端面试的必考点？

在前端技术面试中，算法能力越来越成为衡量开发者水平的重要标准。而二叉树遍历作为数据结构与算法的基础核心内容，几乎成为了各大互联网公司前端岗位的"标配"考题。据统计，超过80%的一线互联网公司在前端面试中会考察二叉树相关算法，其中遍历算法更是重中之重。

为什么二叉树遍历如此重要？因为它不仅考察了候选人对基本数据结构的理解，还涉及到递归、迭代、栈、队列等多个编程核心概念，能够全面反映开发者的逻辑思维能力和代码实现水平。

二叉树基础回顾

在深入探讨遍历算法之前，让我们先快速回顾二叉树的基本概念：

// 二叉树节点的基本定义
class TreeNode {
    constructor(val) {
        this.val = val;        // 节点值
        this.left = null;      // 左子节点
        this.right = null;     // 右子节点
    }
}

// 示例：构建一个简单的二叉树
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

二叉树（Binary Tree）是一种重要的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树在计算机科学中有着广泛的应用，如文件系统、数据库索引、编译器语法分析等。

四种经典遍历方式详解

1. 前序遍历（Preorder Traversal）

算法思想

前序遍历遵循"根-左-右"的访问顺序：

  1. 首先访问根节点
  2. 然后递归遍历左子树
  3. 最后递归遍历右子树

递归实现

/**
 * 前序遍历 - 递归版本
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function preorderTraversalRecursive(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        result.push(node.val);     // 访问根节点
        traverse(node.left);       // 遍历左子树
        traverse(node.right);      // 遍历右子树
    }
    
    traverse(root);
    return result;
}

迭代实现

/**
 * 前序遍历 - 迭代版本（使用栈）
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function preorderTraversalIterative(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        
        // 注意：先压入右子节点，再压入左子节点
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    
    return result;
}

时间复杂度分析

  • 时间复杂度：O(n)，每个节点恰好被访问一次
  • 空间复杂度：
    • 递归版本：O(h)，h为树的高度（递归调用栈深度）
    • 迭代版本：O(h)，栈的最大深度为树的高度

应用场景

  • 复制二叉树结构
  • 序列化二叉树
  • 表达式树的前缀表示法

2. 中序遍历（Inorder Traversal）

算法思想

中序遍历遵循"左-根-右"的访问顺序：

  1. 先递归遍历左子树
  2. 然后访问根节点
  3. 最后递归遍历右子树

递归实现

/**
 * 中序遍历 - 递归版本
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function inorderTraversalRecursive(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        traverse(node.left);       // 遍历左子树
        result.push(node.val);     // 访问根节点
        traverse(node.right);      // 遍历右子树
    }
    
    traverse(root);
    return result;
}

迭代实现

/**
 * 中序遍历 - 迭代版本
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function inorderTraversalIterative(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current || stack.length > 0) {
        // 一直向左走到尽头
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        // 弹出栈顶节点并访问
        current = stack.pop();
        result.push(current.val);
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

时间复杂度分析

  • 时间复杂度：O(n)，每个节点恰好被访问一次
  • 空间复杂度：
    • 递归版本：O(h)
    • 迭代版本：O(h)

应用场景

  • 二叉搜索树（BST）的有序输出
  • 表达式树的中缀表示法
  • 验证二叉搜索树的合法性

3. 后序遍历（Postorder Traversal）

算法思想

后序遍历遵循"左-右-根"的访问顺序：

  1. 先递归遍历左子树
  2. 然后递归遍历右子树
  3. 最后访问根节点

递归实现

/**
 * 后序遍历 - 递归版本
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function postorderTraversalRecursive(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        traverse(node.left);       // 遍历左子树
        traverse(node.right);      // 遍历右子树
        result.push(node.val);     // 访问根节点
    }
    
    traverse(root);
    return result;
}

迭代实现（双栈法）

/**
 * 后序遍历 - 迭代版本（双栈法）
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function postorderTraversalIterative(root) {
    if (!root) return [];
    
    const result = [];
    const stack1 = [root];
    const stack2 = [];
    
    while (stack1.length > 0) {
        const node = stack1.pop();
        stack2.push(node);
        
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    
    while (stack2.length > 0) {
        result.push(stack2.pop().val);
    }
    
    return result;
}

迭代实现（单栈法）

/**
 * 后序遍历 - 迭代版本（单栈法）
 * @param {TreeNode} root 二叉树根节点
 * @return {number[]} 遍历结果数组
 */
function postorderTraversalSingleStack(root) {
    const result = [];
    const stack = [];
    let lastVisited = null;
    let current = root;
    
    while (current || stack.length > 0) {
        if (current) {
            stack.push(current);
            current = current.left;
        } else {
            const peekNode = stack[stack.length - 1];
            
            if (peekNode.right && peekNode.right !== lastVisited) {
                current = peekNode.right;
            } else {
                result.push(peekNode.val);
                lastVisited = stack.pop();
            }
        }
    }
    
    return result;
}

时间复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：
    • 递归版本：O(h)
    • 迭代版本：O(h)

应用场景

  • 释放二叉树内存
  • 计算二叉树的高度
  • 表达式树的后缀表示法（逆波兰表示法）

4. 层序遍历（Level Order Traversal）

算法思想

层序遍历按照树的层次从上到下、从左到右访问节点，也称为广度优先搜索（BFS）。

队列实现

/**
 * 层序遍历
 * @param {TreeNode} root 二叉树根节点
 * @return {number[][]} 按层分组的结果数组
 */
function levelOrderTraversal(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}

时间复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(w)，w为树的最大宽度

应用场景

  • 寻找最短路径（如二叉树的最小深度）
  • 序列化二叉树为数组表示
  • 按层打印二叉树结构

四种遍历方式的对比分析

为了更清晰地理解这四种遍历方式的区别，我们通过一个具体的二叉树示例来分析：

graph TD
    A[1] --> B[2]
    A --> C[3]
    B --> D[4]
    B --> E[5]
    C --> F[6]
    C --> G[7]

遍历结果对比表

遍历方式 访问顺序 示例结果 空间复杂度 应用特点
前序遍历 根-左-右 [1, 2, 4, 5, 3, 6, 7] O(h) 适合复制、序列化
中序遍历 左-根-右 [4, 2, 5, 1, 6, 3, 7] O(h) BST有序输出
后序遍历 左-右-根 [4, 5, 2, 6, 7, 3, 1] O(h) 适合释放内存、计算高度
层序遍历 按层访问 [[1], [2, 3], [4, 5, 6, 7]] O(w) 广度优先、最短路径

算法选择指南

flowchart TD
    A[选择遍历算法] --> B{具体需求}
    B --> C[需要有序输出BST]
    B --> D[需要复制或序列化]
    B --> E[需要释放内存或计算高度]
    B --> F[需要广度优先搜索]
    
    C --> G[使用中序遍历]
    D --> H[使用前序遍历]
    E --> I[使用后序遍历]
    F --> J[使用层序遍历]
    
    G --> K[时间复杂度: O(n)<br>空间复杂度: O(h)]
    H --> L[时间复杂度: O(n)<br>空间复杂度: O(h)]
    I --> M[时间复杂度: O(n)<br>空间复杂度: O(h)]
    J --> N[时间复杂度: O(n)<br>空间复杂度: O(w)]

面试常见问题及解题技巧

1. 递归与迭代的选择策略

面试官常问："为什么有时候选择递归，有时候选择迭代？"

回答要点：

  • 递归：代码简洁易懂，但可能存在栈溢出风险（深度很大的树）
  • 迭代：避免栈溢出，但代码相对复杂，需要手动维护栈或队列
  • 选择原则：树深度不大时优先递归，深度可能很大时选择迭代

2. 空间复杂度优化技巧

优化策略：

  • 对于前序、中序、后序遍历，迭代版本的空间复杂度都是O(h)
  • 层序遍历的空间复杂度是O(w)，w为树的最大宽度
  • Morris遍历可以在O(1)空间复杂度下完成中序遍历

3. 常见变种题目

题目1：锯齿形层序遍历

function zigzagLevelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    let leftToRight = true;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            if (leftToRight) {
                currentLevel.push(node.val);
            } else {
                currentLevel.unshift(node.val);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
        leftToRight = !leftToRight;
    }
    
    return result;
}

题目2：寻找每层的最大值

function largestValues(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        let maxVal = -Infinity;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            maxVal = Math.max(maxVal, node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(maxVal);
    }
    
    return result;
}

实战演练：LeetCode经典题目

题目1：二叉树的最大深度（104题）

// 使用后序遍历的递归解法
function maxDepth(root) {
    if (!root) return 0;
    
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    return Math.max(leftDepth, rightDepth) + 1;
}

// 使用层序遍历的迭代解法
function maxDepthLevelOrder(root) {
    if (!root) return 0;
    
    let depth = 0;
    const queue = [root];
    
    while (queue.length > 0) {
        depth++;
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return depth;
}

题目2：对称二叉树（101题）

function isSymmetric(root) {
    if (!root) return true;
    
    function isMirror(left, right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        if (left.val !== right.val) return false;
        
        return isMirror(left.left, right.right) && 
               isMirror(left.right, right.left);
    }
    
    return isMirror(root.left, root.right);
}

性能优化与最佳实践

1. 避免不必要的递归调用

错误示范：

// 不必要的重复递归调用
function badExample(node) {
    if (!node) return 0;
    return 1 + badExample(node.left) + badExample(node.right);
}

优化版本：

// 使用尾递归优化
function goodExample(node, depth = 0) {
    if (!node) return depth;
    return Math.max(
        goodExample(node.left, depth + 1),
        goodExample(node.right, depth + 1)
    );
}

2. 使用迭代避免栈溢出

对于深度可能很大的二叉树，始终优先考虑迭代解法：

// 安全的迭代前序遍历
function safePreorder(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    
    return result;
}

3. 内存使用优化

对于大规模数据处理，考虑使用原地算法或减少中间数据结构：

// 原地修改的Morris中序遍历（O(1)空间）
function morrisInorder(root) {
    const result = [];
    let current = root;
    
    while (current) {
        if (!current.left) {
            result.push(current.val);
            current = current.right;
        } else {
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            
            if (!predecessor.right) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                result.push(current.val);
                current = current.right;
            }
        }
    }
    
    return result;
}
frontend-hard-mode-interview
《前端内参》，有关于JavaScript、编程范式、设计模式、软件开发的艺术等大前端范畴内的知识分享，旨在帮助前端工程师们夯实技术基础以通过一线互联网企业技术面试。
项目地址：https://gitcode.com/gh_mirrors/fr/frontend-hard-mode-interview
登录后查看全文
热门项目推荐
相关项目推荐

热门内容推荐

1 【亲测免费】 开源项目 `build-your-own-x` 使用指南2 【亲测免费】 探索科技之旅：《Build Your Own X》项目详解3 GitHub_Trending/bu/build-your-own-x自动化：CI/CD流程在自制项目中的应用4 从零打造智能家居系统：用build-your-own-x实现家庭自动化

项目优选

收起
kernelkernel
deepin linux kernel
C
27
11
docsdocs
OpenHarmony documentation | OpenHarmony开发者文档
Dockerfile
567
3.83 K
leetcodeleetcode
🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解
Java
68
20
nop-entropynop-entropy
Nop Platform 2.0是基于可逆计算理论实现的采用面向语言编程范式的新一代低代码开发平台，包含基于全新原理从零开始研发的GraphQL引擎、ORM引擎、工作流引擎、报表引擎、规则引擎、批处理引引擎等完整设计。nop-entropy是它的后端部分，采用java语言实现，可选择集成Spring框架或者Quarkus框架。中小企业可以免费商用
Java
12
1
flutter_flutterflutter_flutter
暂无简介
Dart
798
197
RuoYi-Vue3RuoYi-Vue3
🎉 (RuoYi)官方仓库 基于SpringBoot，Spring Security，JWT，Vue3 & Vite、Element Plus 的前后端分离权限管理系统
Vue
1.37 K
779
giteagitea
喝着茶写代码！最易用的自托管一站式代码托管平台，包含Git托管，代码审查，团队协作，软件包和CI/CD。
Go
23
0
kernelkernel
openEuler内核是openEuler操作系统的核心，既是系统性能与稳定性的基石，也是连接处理器、设备与服务的桥梁。
C
349
200
pytorchpytorch
Ascend Extension for PyTorch
Python
376
446
rainbondrainbond
无需学习 Kubernetes 的容器平台，在 Kubernetes 上构建、部署、组装和管理应用，无需 K8s 专业知识，全流程图形化管理
Go
16
1