层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;

    queue<TreeNode*> q;
    q.push(root);
    //队列不空
    while(!q.empty()){
        //curLevelSize记录当前层结点的个数
        int curLevelSize = q.size();
        //level数组存放每一层的结点值
        vector<int> level;
        for(int i = 0; i < curLevelSize; i ++){
            TreeNode* p = q.front();
            //取出队头元素
            q.pop();
            //操作队头元素
            if(p->left) q.push(p->left);
            if(p->right) q.push(p->right);
            level.push_back(p->val);
        }
        res.push_back(level);
    }
    return res;
}

前序遍历

//根左右的顺序对二叉树进行遍历
void preorder(TreeNode* root)
{
    if(!root) return;
    res.push_back(root->val);
    preorder(root->left);
    preorder(root->right);
}

中序遍历

//左根右的顺序对二叉树进行遍历
void midorder(TreeNode* root)
{
    if(!root) return;
    midorder(root->left);
    //对根节点的操作
    res.push_back(root->val);
    midorder(root->right);
}
//对二叉搜索树进行中序遍历得到的结果是一个递增的序列

后序遍历

//左右根的顺序对二叉树进行遍历
void postorder(TreeNode* root)
{
    if(!root) return;
    postorder(root->left);
    postorder(root->right);
    //对根节点的操作
    res.push_back(root->val);
}