二叉树深度优先遍历方法（DFS）

本文介绍二叉树深度优先遍历的递归实现和循环改造实现。

二叉树节点定义

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1. 前序遍历（根-左-右）

递归实现

function preorderRecursive(root) {
    const result = [];
    
    function dfs(node) {
        if (!node) return;
        
        result.push(node.val);    // 访问根节点
        dfs(node.left);           // 递归遍历左子树
        dfs(node.right);          // 递归遍历右子树
    }
    
    dfs(root);
    return result;
}

循环改造实现

function preorderIterative(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;
}

5. 递归与循环的对比分析

递归实现的特点

优点：

• 代码简洁，易于理解
• 直接体现了递归定义
• 实现简单，不易出错

缺点：

• 可能导致栈溢出（深度很大的树）
• 函数调用开销
• 空间复杂度受递归深度影响

循环实现的特点

优点：

• 避免栈溢出问题
• 可以处理更深的树
• 更好的性能控制

缺点：

• 代码复杂度较高
• 需要手动管理栈

6. 完整测试示例

// 构建测试二叉树
//       1
//      / \
//     2   3
//    / \
//   4   5
 
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);
 
// 测试所有实现
console.log('=== 前序遍历 ===');
console.log('递归:', preorderRecursive(root));     // [1, 2, 4, 5, 3]
console.log('循环:', preorderIterative(root));     // [1, 2, 4, 5, 3]
 

7. 性能和空间复杂度

时间复杂度

• 所有实现都是 O(n)，其中 n 是节点数量

空间复杂度

• 递归实现：O(h)，其中 h 是树的高度（系统调用栈）
• 循环实现：O(h)，其中 h 是树的高度（手动维护的栈）
• 最坏情况：O(n)（完全不平衡的树）
• 最好情况：O(log n)（完全平衡的树）

8. 递归转循环的核心思想

1. 用显式栈替代隐式的系统调用栈
2. 保存必要的状态信息（如当前节点、访问状态等）
3. 模拟递归调用的执行顺序
4. 正确处理子树的访问顺序

通过这些方法，你可以根据具体需求选择合适的实现方式。递归实现更直观易懂，循环实现更适合处理深度较大的树结构。