题解

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 队列迭代法

class Solution {//两种方法。1、队列迭代法。
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        //定义保存结果的二维数组，root为空直接返回空数组
        queue<TreeNode*> q;
        q.push(root);//定义队列q并暂存根节点的值
        while(!q.empty()){//当q不为空时继续循环迭代
            vector<int> thisLevel;//定义保存当前层次值的一维数组
            //for(int i=0;i<q.size();i--){
            //注意这里不能这么写，因为q是动态的，会随着循环进行改变判断条件。但是赋值语句for循环只执行一次，不会改变。
            for(int i=q.size(); i>0; i--){//对这一层已经压入队列的数进行遍历
                TreeNode *cur = q.front();q.pop();//取队首的值，并出队列
                thisLevel.push_back(cur->val);//压入一维数组
                if(cur->left) q.push(cur->left);//当左子节点存在，压入队尾
                if(cur->right) q.push(cur->right);//右子节点同上
            }
            res.push_back(thisLevel);//一个层次存完压入res中
        }
        return res;//返回结果
    }
};

2. 递归法

class Solution {//两种方法。2、递归法。其实是深度优先搜索，但是引入一个level用于存储当前在第几层。
    vector<vector<int>> res;//定义存结果的二维数组res
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        
        if(!root) return res;//特殊情况的判断
        helper(root,0);//进入递归函数
        return res;//返回结果
    }

    void helper(TreeNode* cur, int level){//定义递归函数
        if(!cur) return;//若当前节点为空，直接返回
        if(res.size() == level) res.push_back({});//当res.size()==level时创建新行。因为level从0开始计数，当二者相等时实际递归到的层数已经大于res.size(),需要添加一行。
        res[level].push_back(cur->val);//为该level添加新的值
        helper(cur->left,level+1);//递归左子树
        helper(cur->right,level+1);//递归右子树
    }
};