思路

题目分析

1. 题目给出了一棵二叉树
2. 我们需要返回层序遍历这棵二叉树的结果，每层组织一个向量，最终这些向量再组织成一个向量
3. 返回最终组织的向量。

• 方法一：递归
  • 我们可以采用dfs深度优先遍历的方法进行处理
  • 需要注意的点是我们要才有前序优先的方式保证顺序，还要用一个level变量记录当前结点所在的层数，以便我们成功找到哪一个res索引的子向量需要添加新元素
• 方法二：迭代
  • 利用队列进行层序遍历
  • 需要注意的点是我们要记录每一层压入队列的结点数量
  • 这样可以保证我们层与层之间互不干预

方法一：递归

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> res;
        dfs(res, root, 0);        // 采用深度优先遍历的方案
        return res;
    }
    
    void dfs(vector<vector<int>>& res, TreeNode* root, int level) {
        if(root == NULL) return;                    // 判断根节点是否是NULL，是则返回
        if(level >= res.size()) res.push_back({});  // 判断是否需要在res中多填一向量组，因为我们下面要用索引访问
        res[level].push_back(root->val);            // 用level决定将当前的结点值放置到哪一个索引对应的res的子向量中
        dfs(res, root->left, level+1);              // 继续递归左子树（左子树必须先递归）
        dfs(res, root->right, level+1);             // 继续递归右子树
    }
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，每个节点都需要访问一次
• 空间复杂度：$O(logN)O(logN)$，递归栈的空间使用，最深的规模也与树的深度有关

方法二：迭代

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> res; 
        if(root == NULL) return {};            // 判断根节点是否为空
        queue<TreeNode*> q;                    // 层序队列
        q.push(root);                          // 压入根节点
        
        while(!q.empty()) {
            int n = q.size();                  // 获取每层的结点数量
            vector<int> temp;
            while(n) {
                TreeNode* p = q.front();       // 队首元素出队，并等待后面压入其左右子节点指针
                q.pop();
                temp.push_back(p->val);        // 对该层层内的所有节点指针指向的结点val进行push_back操作
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
                n--;
            }
            res.push_back(temp);               // 每完成一层收集则压入最终的结果res中
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，每个节点都要访问一次
• 空间复杂度：$O(logN)O(logN)$，队列中最多的空间占用不超过树的一层结点数量，因此是$O(logN)O(logN)$级别