题目主要信息:

将一棵n个节点的二叉树按照从上到下按层的方式打印,每层按照从左到右的顺序输出。

思路:

题目要求将二叉树按行打印,即按层打印,其中每层分开。不难想到,要使用层次遍历,但是难点在于如何每层分开存储,从哪里知晓分开的时机?在层次遍历的时候,我们通常会借助队列(queue),事实上,队列中的值大有玄机,让我们一起来看看:

  • 当根节点进入队列时,队列长度为1,第一层结点数也为1
  • 若是根节点有两个子节点,push进队列后,队列长度为2,第二层结点数也为2;若是根节点一个子节点,push进队列后,队列长度为为1,第二层结点数也为1.
  • 由此,我们可知,每层的结点数等于进入该层时队列长度,因为刚进入该层时,这一层每个结点都会push进队列,而上一层的结点都出去了。

综上,反过来,每次只要在队列长度内循环,必定是一层,一层访问完毕再更新队列长度即可。 图片说明

方法一:非递归层次遍历

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {//层次遍历
            TreeNode* head = pRoot;
            vector<vector<int> > res;
            if(head == NULL)
                  return res; //如果是空,则直接返回空vector
            queue<TreeNode*> temp; //队列存储,进行层次遍历
            temp.push(head);
            TreeNode* p;
            while(!temp.empty()){
                vector<int> row;  //记录二叉树的某一行
                int n = temp.size();
                for(int i = 0; i < n; i++){//因先进入的是根节点,故每层结点多少,队列大小就是多少
                    p = temp.front();
                    temp.pop();
                    row.push_back(p->val);
                    //若是左右孩子存在,则存入左右孩子作为下一个层次
                    if(p->left)
                        temp.push(p->left);
                    if(p->right)
                        temp.push(p->right);
                }
                res.push_back(row);
            }
            return res;
        }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),每个结点访问一次
  • 空间复杂度:O(n)O(n),队列的空间

方法二:递归层次遍历

具体方法:

除了用队列非递归可以实现二叉树的层次遍历,使用递归也可以,只是需要在函数加入记录深度的遍历,每往下一层深度加1,同时保存结果的vector正好对应每层一个数组,因此vector的大小正好是遍历的深度,由此可以实现递归。

class Solution {
public:
    void traverse(TreeNode* root, vector<vector<int>>& ans, int depth) {
        if(root) {
            if(ans.size() < depth)             //新的一层
                ans.push_back(vector<int>{});  
            //vector从0开始计数因此减1,在节点当前层的vector中插入节点
            ans[depth - 1].push_back(root->val); 
        }
        else
            return;
        traverse(root->left, ans, depth + 1); //递归左右时结点记得加1
        traverse(root->right, ans, depth + 1);
    }
    vector<vector<int> > Print(TreeNode* pRoot) {//层次遍历
        vector<vector<int>> ans;
        traverse(pRoot, ans, 1); //树的层级从1开始递归计数
        return ans;
     }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),每个结点访问一次
  • 空间复杂度:O(n)O(n),递归栈的最大深度