二叉树的前序遍历

题意

输出一个二叉树的前序遍历

方法

递归

分析

前序遍历，即使根先于左右节点访问

因此返回的内容是 [根，左子树的前序遍历，右子树的前序遍历]

因此设计函数，接受一个树的节点，返回当前节点为根的前序遍历的结果

每次递归左右子树完成拼接

这样，对根调用这个函数就是要求的结果

样例

以样例数据为例

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)return {}; // 空节点
        vector<int> res = {root->val}; // 根节点
        auto resl = preorderTraversal(root->left); // 左节点
        for(auto item : resl)res.push_back(item); // 拼接左侧结果
        auto resr = preorderTraversal(root->right); // 左节点
        for(auto item : resr)res.push_back(item); // 拼接左侧结果
        return res;
    }
};

复杂度分析

空间复杂度: 主要消耗在生成的结果上，空间复杂度为$O(n)O(n)$

时间复杂度: 最坏情况，整个树是链状的，那么反复的拼接，一个节点的操作次数会很大，，所以总时间复杂度为$O(n^2)O(n^2)$

递归+引用数组

分析

上面的方法解决了逻辑的部分，但是在数组处理的部分反复的拼接代价很大

如果不需要拼接，直接知道每个值应该放在什么位置就好了

考虑按照结果的顺序递归，并直接在结果的相应位置增加值

因此使用引用数组，按照前序顺序遍历，因为按照了前序的顺序，因此直接在数组的末尾增加值，它就是最终要求的值，不需要再拼接或其它任何调整

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, vector<int>&arr){
        if(!root)return; // 空节点
        arr.push_back(root->val); // 前序
        dfs(root->left,arr); // 左节点
        dfs(root->right,arr); // 右侧节点
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> arr = {}; // 结果
        dfs(root, arr);
        return arr;
    }
};

复杂度分析

空间复杂度: 主要消耗在生成的结果上，空间复杂度为$O(n)O(n)$

时间复杂度: 每个位置的值处理代价为常数，所以总时间复杂度为$O(n)O(n)$