题解 | #实现二叉树先序,中序和后序遍历#

实现二叉树先序,中序和后序遍历

https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362

解题思路

  • 依次实现前序、中序、后序遍历;
  • 将三者遍历的结果按顺序存入到结果vector中。

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    vector<int> pre, in, post;
    void preOrders(TreeNode* root) {
        if(!root)
        {
            return;
        }

        pre.push_back(root->val);
        preOrders(root->left);
        preOrders(root->right);  
    }

    void inOrders(TreeNode* root) {
        if(!root)
        {
            return;
        }

        inOrders(root->left);
        in.push_back(root->val);
        inOrders(root->right);
    }

    void postOrders(TreeNode* root) {
        if(!root)
        {
            return;
        }

        postOrders(root->left);
        postOrders(root->right);
        post.push_back(root->val);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int> >  res;
        preOrders(root);
        inOrders(root);
        postOrders(root);
        res.push_back(pre);
        res.push_back(in);
        res.push_back(post);

        return res;
    }
};

复杂度分析

  • 时间复杂度为O(N);
  • 空间复杂度为O(N)。
全部评论

相关推荐

09-17 19:25
已编辑
太原理工大学 游戏测试
叁六玖:公司名发我,我要这个HR带我打瓦
我的秋招日记
点赞 评论 收藏
分享
08-27 12:02
已编辑
南京外国语学校 网络安全
再来一遍:实则劝各位不要all in华子,不要相信华为hr
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
正在热议
更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务