题意

给定一颗二叉树，求其从左到右，从上层到下层遍历的结果。

思路

我们可以利用深度优先搜索的方法解决这个问题，例子如下：

例如，对于二叉树{1,2,3,4,5,#,#,#,6} 我们按照深度优先搜索的方法，先搜索其左子树，并记录搜索的深度已记录在不同层的答案数组中，每搜索一个数更新一次层序遍历，遍历整颗树后即可得出答案。 例如，在搜索到这里时，我们记录的层序遍历就为

[

[1],

[2],

[4],

]

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> ans;
    void dfs(TreeNode* nowNode, int nowDepth)
    {
        if(nowNode == NULL) return;//当前节点为空，则返回
        int size=ans.size();
        if(size<=nowDepth)
        {
            vector<int> tmpNewVec;
            ans.push_back(tmpNewVec);//答案中新增一层
        }
        ans[nowDepth++].push_back(nowNode->val);//将当前节点加入答案
        dfs(nowNode->left,nowDepth);
        dfs(nowNode->right,nowDepth);//分别搜索左右子树并将结果存入下一层答案
    }
    vector<vector<int> > levelOrder(TreeNode* root)
    {
        // write code here
        dfs(root,0);//从根节点开始搜索
        return ans;
    }
};

复杂度分析

时间复杂度:$O(n)O(n)$,其中$nn$为二叉树节点数，每个节点刚好访问一次。

空间复杂度:$O(n)O(n)$,为存放答案所用vector占用空间。