题解 | #求二叉树的层序遍历#

解题思路：

二叉树的层序遍历是一道基础的题目，可以使用BFS和DFS两种思路来解决，其中BFS在此题中相对更为简洁。

方法一:使用BFS遍历

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        if(root==nullptr)    
            return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
             //sz记住当前层的节点数量，方便确定执行该层的遍历次数。
            int sz=q.size();
            vector<int> cur;
            while(sz--){
                TreeNode* tmp=q.front();
                q.pop();
                cur.push_back(tmp->val);
                if(tmp->left)
                    q.push(tmp->left);
                if(tmp->right)
                    q.push(tmp->right);
            }
            ans.push_back(cur);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)，n为节点数量，BFS对每个节点访问一次。
空间复杂度：O(n)，空间复杂度在于队列中存储节点的最大值，当该二叉树为满二叉树时，最大数量为(n+1)/2。

方法二：使用DFS遍历

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        dfs(ans,root,0);
        return ans;
    }
    void dfs(vector<vector<int>>& ans,TreeNode* root,int level){
        if(root==nullptr) return;
        //当前层数超过了ans的大小，需要新增一个vector<int>
        if(level>=ans.size())
            ans.push_back(vector<int>());
        ans[level].push_back(root->val);
        dfs(ans,root->left,level+1);
        dfs(ans,root->right,level+1);
    }
};

复杂度分析

时间复杂度：O(n)，n为节点数量，DFS对每个节点访问一次，因此递归调用n次，每次调用执行常数次操作，时间复杂度O(n)。
空间复杂度：O(n)，空间复杂度在于递归调用深度和每次递归调用辅助空间，辅助空间为常数级，与节点深度相关，当节点深度为n时最大，为O(n)。