二叉树层序遍历的两种写法（BFS和DFS）

力扣链接：102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        queueq;
        if(root) q.push(root);
        vector>res;
        while(!q.empty()){
            int size = q.size();//用常量size记录当前的队列中的结点数量
            vectortmp;
            for(int i=0;ival);
                q.pop();
                if(k->left)
                {
                    q.push(k->left);
                }
                if(k->right)
                {
                    q.push(k->right);
                }
            }
            res.push_back(tmp);//同时压入这一层结点的所有左右结点，我一开始也没看懂那个输出...
        }
        return res;
    }

};

class Solution {
public:
    vector>res;
    vector> levelOrder(TreeNode* root) {
        if(!root) return {};//空树返回空
        levelTraversal(root,0);
        return res;
    }
    void levelTraversal(TreeNode* root,int layer)
    {
        if(root)
        {
            if(res.size() == layer)//如果res中这一层还没有开辟vector存储空间，那么就进行开辟
            {
                res.push_back(vector());
            }
            res[layer].push_back(root->val);//将结点值存入对应层的结果数组
        }
        if(root->left)
        {
            levelTraversal(root->left,layer + 1);   
        }
        if(root->right)
        {
            levelTraversal(root->right,layer + 1);   
        }
    }

};