二叉树前序遍历：递归与迭代实现及复杂度分析

二叉树的前序遍历是一种深度优先遍历方法，其遍历顺序为：根节点 -> 左子树 -> 右子树。前序遍历常用于复制树、序列化树结构等场景。

递归实现

递归实现是最直观的方式，代码简洁易懂。

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

迭代实现

迭代实现使用栈来模拟递归调用栈，适合处理深度较大的树结构，避免递归栈溢出。

function preorderTraversal(root) {
    const result = [];
    const stack = [];
    
    if (root) stack.push(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;
}

示例

假设有以下二叉树：

    1
   / \
  2   3
 / \
4   5

前序遍历结果为：[1, 2, 4, 5, 3]

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数，每个节点被访问一次。
• 空间复杂度：
  • 递归实现：O(h)，其中 h 是树的高度，递归栈的深度。
  • 迭代实现：O(h)，栈的最大深度为树的高度。

应用场景

• 树的序列化：将树结构转换为线性结构以便存储或传输。
• 表达式树求值：前序遍历可以用于解析表达式树。

如果你有更多关于二叉树遍历或其他前端技术的问题，欢迎继续提问！