力扣 144题 二叉树的前序遍历 记录

题目描述

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

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

思路

辅助函数 traversal:

 - 参数: 接受两个参数，一个是指向树节点的指针 cur（表示当前访问的节点），另一个是一个整型向量的引用 vec（用于存储遍历的结果）。
 - 功能:该函数用于递归地执行前序遍历。
 - 实现:
	   递归基: 如果当前节点 cur 是 NULL，则直接返回。这表示到达了叶节点的子节点。
	   记录节点值: 将当前节点的值添加到 vec 中。这是前序遍历的“访问根节点”部分。
	   递归左子树: 调用 traversal 函数自身，以当前节点的左子节点 cur->left 作为新的当前节点。
	   递归右子树: 调用 traversal 函数自身，以当前节点的右子节点 cur->right 作为新的当前节点。

主函数 preorderTraversal:

 - 参数: 接受一个指向树的根节点的指针 root。
 - 功能: 初始化一个空的整型向量 result，并调用 traversal 函数来填充这个向量，最后返回填充后的向量。
 - 实现:
	  创建一个名为 result 的空向量，用来存放前序遍历的结果。 
	  调用 traversal 函数，传入根节点 root 和向量result。 
	  返回向量 result，其中包含了树的前序遍历结果。

完整代码

#include<iostream>
#include<vector>

// 定义二叉树的节点结构
struct TreeNode {
    int val;                // 节点值
    TreeNode *left;         // 左子节点
    TreeNode *right;        // 右子节点
    TreeNode() : val(0), left(nullptr), right(nullptr) {}           // 默认构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}      // 带有初始值的构造函数
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // 完整构造函数
};

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;
        traversal(root, result);
        return result;
    }

    void traversal(TreeNode* cur, std::vector<int>& vec)
    {
        if(cur == NULL) return;
        vec.push_back(cur->val);
        traversal(cur->left, vec);
        traversal(cur->right, vec);
    }
};

int main()
{
    // 创建示例二叉树： 1, null, 2, 3
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    Solution s;
    std::vector<int> result = s.preorderTraversal(root);

    // 输出结果
    for (int value : result) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}