解法一:递归

递归方法通过定义递归函数helper,遍历树的每一层,并将结果放入结果数组res的相应位置,因此需要定义level变量以记录当前访问到的层数。
在完成对某一凑层的遍历时,按照相同方式递归地访问左孩子和右孩子,且层数加1。

实现代码如下:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > res; 
            if (!pRoot) 
                return res; 
            helper(res, 0, pRoot); 
            return res;
        }
        void helper(vector<vector<int> > & res, int level, TreeNode* node) {
            if (!node) // 结点为空,直接返回
                return; 
            if (res.size() == level) { // 遍历到新的一层时
                vector<int> tmp; 
                res.push_back(tmp); 
            }
            res[level].push_back(node->val); // 保存结果(第level层)
            helper(res, level + 1, node->left); // 左孩子
            helper(res, level + 1, node->right); // 右孩子
        }

};

该方法遍历到树的每一个结点,时间复杂度为O(N);该方法在递归过程中需要用到栈空间,空间复杂度为O(N)。

解法二:非递归

此题即实现二叉树的「层次遍历」。

二叉树层次遍历的非递归实现利用到「队列」这一数据结构,具体步骤如下:

  1. 初始情况,根结点入队列;
  2. 定义变量size记录当前队列长度;
  3. 对于「当前队列」,遍历其所有元素:依次出队列、访问该元素、左右孩子入队列。注意:新入队列的「左右孩子」应当在下一层被访问,因此循环次数为size次。
  4. 重复上述步骤直至队列为空。

步骤如图所示。

图片说明

代码实现如下:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > res;
            if (!pRoot)
                return res;
            queue<TreeNode*> q; // 定义队列
            q.push(pRoot); // 根结点入队
            while (!q.empty()) {
                int size = q.size();
                vector<int> arr;
                for (int i = 0; i < size; i++) {
                    TreeNode* p = q.front();
                    q.pop();
                    if (p->left) q.push(p->left); // 左孩子入队
                    if (p->right) q.push(p->right); // 右孩子入队
                    if (!p) continue;
                    arr.push_back(p->val);
                }
                res.push_back(arr);
                arr.clear();
            }
            return res;
        }
};

该方法遍历到树的每一个结点,时间复杂度为O(N);该方法定义了队列q,空间复杂度为O(N)。