题解 | 二叉树的前序遍历

1、解题思路

前序遍历是二叉树的一种深度优先遍历方式，顺序为：

1. 访问根节点。
2. 前序遍历左子树。
3. 前序遍历右子树。

可以用递归或迭代的方式实现前序遍历。

2、代码实现

C++

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        preorder(root, result);
        return result;
    }

  private:
    void preorder(TreeNode* root, vector<int>& result) {
        if (root == nullptr) {
            return ;
        }

        result.push_back(root->val);    // 访问根节点
        preorder(root->left, result);   // 遍历左子树
        preorder(root->right, result);  // 遍历右子树
    }
};

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型一维数组
#
from typing import List, Optional

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # write code here
        result = []
        self.preorder(root, result)
        return result

    def preorder(self, root: Optional[TreeNode], result: List[int]) -> None:
        if root is None:
            return
        result.append(root.val)  # 访问根节点
        self.preorder(root.left, result)  # 遍历左子树
        self.preorder(root.right, result)  # 遍历右子树

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：O(n)，递归栈的深度在最坏情况下为树的高度（O(n)），平均情况下为 O(log n)。