Easy

题目描述

给你二叉树的根节点 root，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]

示例 3：

输入：root = []
输出：[]

示例 4：

输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶： 递归算法很简单，你可以通过迭代算法完成吗？

解题思路

前序遍历是二叉树遍历的经典问题，遍历顺序为：根节点 → 左子树 → 右子树。

方法一：递归（推荐）

递归是最直观的解法。对于每个节点，先访问当前节点，再递归遍历左子树和右子树。递归的终止条件是遇到空节点。

方法二：迭代 + 栈

由于递归本质上使用了系统栈，我们可以用显式栈来模拟递归过程。关键是要注意入栈顺序：先将右子树入栈，再将左子树入栈，这样出栈时就能保证左子树先于右子树被访问。

方法三：Morris 遍历

Morris 遍历可以在 O(1) 空间复杂度下完成遍历，通过修改树的结构来避免使用额外空间，但实现较为复杂。

对于初学者，建议掌握递归和迭代两种方法。递归代码简洁易懂，迭代方法有助于理解树遍历的本质。

代码实现

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorderHelper(root, result);
        return result;
    }
    
private:
    void preorderHelper(TreeNode* node, vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        preorderHelper(node->left, result);
        preorderHelper(node->right, result);
    }
};

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def preorder(node):
            if not node:
                return
            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return result

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        var result = new List<int>();
        PreorderHelper(root, result);
        return result;
    }
    
    private void PreorderHelper(TreeNode node, IList<int> result) {
        if (node == null) return;
        result.Add(node.val);
        PreorderHelper(node.left, result);
        PreorderHelper(node.right, result);
    }
}

var preorderTraversal = function(root) {
    const result = [];
    
    function preorder(node) {
        if (!node) return;
        result.push(node.val);
        preorder(node.left);
        preorder(node.right);
    }
    
    preorder(root);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
递归O(n)O(h)
迭代O(n)O(h)

其中 n 是树中节点的数量，h 是树的高度。在最坏情况下（完全不平衡的树），h = n，空间复杂度为 O(n)。在最好情况下（完全平衡的树），h = log n，空间复杂度为 O(log n)。

相关题目