题目描述

给定一棵二叉树，返回它的层序遍历。（即从上到下，从左到右，一层一层地遍历）

样例

给定二叉树 [3,9,20,null,null,15,7]：

    3
   / \
  9  20
    /  \
   15   7

它的层序遍历结果是：

[
  [3],
  [9,20],
  [15,7]
]

算法1

(DFS) $O(n)$

深度优先遍历

原题解 <-------戳这里

C++ 代码

class Solution {
public:
    void dfs(TreeNode *root,int depth,vector<vector<int>> &res)  //depth 为当前的层数
    {
        if(!root) return;
        if( res.size() < depth )          //答案层数不够，需要增加一层
            res.push_back(vector<int>{});
        res[depth].push_back(root->val);  //添加到该层末尾
        pre(root->left,  depth + 1, res); //去到下一层 
        pre(root->right, depth + 1, res);
    }
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> res;
        dfs(root,0,res); //从第0层开始
        return res;
    }
};

算法2

(DFS) $O(n)$

深度优先遍历

每层之间加一个NULL作为该层的结束点

1. 添加root进入队列，并添加结束点
2. 取出该层所以节点，将其值记录起来，并按顺序将其子节点加入队列中，
3. 取到结束点时，将该层的结果 记录到答案中，并添加一个结束点
4. 重复 步骤2,3 当队列只剩一个结束点为止

C++ 代码

class Solution {
public:
    void dfs(TreeNode* root, vector<vector<int> >& res)
    {
        queue<TreeNode*> s;
        s.push(root);       //将头节点添加到队列
        s.push(NULL);       //设置为结束点
        while(s.front() != NULL)  //当队头为结束点时，遍历结束
        {
            vector<int> t;
            TreeNode* p = s.front();   s.pop();   //取出节点
            while( p != NULL)   //p取到结束点 说明该层已遍历
            {
                t.push_back(p->val);             //记录该层的每一个结果
                if( p->left )  s.push(p->left);  //加入左子树
                if( p->right ) s.push(p->right); //加入右子树
                p = s.front();  s.pop();         //取出该层所以节点
            }
            s.push(NULL);      // 添加结束点
            res.push_back(t);  // 把该层遍历的结果放入res
        }

    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > res; 
        dfs(root, res); 
        return ans;
    }