当前位置：首页 > article >正文

⭐算法OJ⭐二叉树的前序遍历【树的遍历】（C++实现）Binary Tree Preorder Traversal

article 2025/3/22 0:59:48

⭐算法OJ⭐二叉树的中序遍历【树的遍历】（C++实现）Binary Tree Inorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Explanation:
在这里插入图片描述

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]

Explanation:
在这里插入图片描述
Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

递归解法

前序遍历的顺序是： $\rightarrow 左子树 \rightarrow 右子树$ 。
使用递归实现。

#include <vector>
using namespace std;

// 递归前序遍历函数
void preorderTraversalHelper(TreeNode* root, vector<int>& result) {
    if (root == NULL) {
        return;
    }
    // 访问根节点
    result.push_back(root->val);
    // 递归遍历左子树
    preorderTraversalHelper(root->left, result);
    // 递归遍历右子树
    preorderTraversalHelper(root->right, result);
}

// 前序遍历主函数
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    preorderTraversalHelper(root, result);
    return result;
}

迭代解法（使用栈）

使用栈来模拟递归过程。以下是迭代方法的实现：

#include <vector>
#include <stack>
using namespace std;

// 迭代前序遍历函数
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == NULL) {
        return result;
    }

    stack<TreeNode*> stack;
    stack.push(root);

    while (!stack.empty()) {
        TreeNode* node = stack.top();
        stack.pop();
        result.push_back(node->val);

        // 先将右子节点压栈，再压左子节点
        if (node->right != NULL) {
            stack.push(node->right);
        }
        if (node->left != NULL) {
            stack.push(node->left);
        }
    }

    return result;
}