二叉树遍历(102.144.94.145)

102. 二叉树的层序遍历
BPS

/**
 * Definition for a binary tree node.
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vec_all;
        //如果为空, 直接返回
        if(root == nullptr) return vec_all;
        //使用队列保存每层的所有节点，每次把队列里的原先所有节点进行出队列操作，再把每个元素的非空左右子节点进入队列。因此即可得到每层的遍历。
        //怎么知道是在这一层呢? 关键是每一次循环都设一个size,没pop一次就size--
        queue<TreeNode*> que;
        TreeNode* cur = root;
        //第一层入队
        que.emplace(cur);
        //如果队列为空, 就退出循环
        while(!que.empty())
        {
            //如果这一层的元素遍历完了, 就退出循环
            int size = que.size();
            //存放一层的数据
            vector<int> vec;
            while(size--)
            {
                //插入队首元素 
                vec.emplace_back(que.front()->val);
                //如果队首有子节点, 插入到que中
                if(que.front()->left!=nullptr) que.emplace(que.front()->left);
                if(que.front()->right!=nullptr) que.emplace(que.front()->right);
                //删除队首节点
                que.pop();
            }
            //将一层放入vec_all中汇总
            vec_all.emplace_back(vec);
        }
        return vec_all;
    }
};

144. 二叉树的前序遍历
递归

/**
 * Definition for a binary tree node.
 * 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:
    //辅助函数
    void pre_order(vector<int>& vec, TreeNode* cur)
    {
        //递归终止
        if(cur == nullptr) return;
        //前序遍历就是最先打印出来
        vec.push_back(cur->val);
        //递归关系
        pre_order(vec, cur->left);
        pre_order(vec, cur->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vec;
        TreeNode* cur = root;
        pre_order(vec, cur);
        return vec;
    }
};

循环(待续)

ps: 中序和后序就是在递归的中间和后面打印出来