LeetCode 102 [二叉树的层次遍历]

原题目链接：LeetCode102

---

分类

LeetCode

---

题意

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

---

样例输入输出

见上

---

想法

代码里有注释
有3种方法：

---

代码

非常传统的两个队列的解决方案：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        vector<int> le_val;
        while(!q.empty()){//每一次循环都是一层
            int len = q.size();
            le_val.clear();
            queue<TreeNode*> temq; // 先把这一层的结点存起来
            for(int i=0;i < len; i++){
                TreeNode* temNode = q.front();
                q.pop();
                if(temNode->left){
                    temq.push(temNode->left);
                }
                if(temNode->right){
                    temq.push(temNode->right);
                }
                le_val.push_back(temNode->val);//存值
            }
            while(!temq.empty()){//将这一层的结点放入 主 队列中
                q.push(temq.front());   
			    temq.pop();
            }
            res.push_back(le_val);
        }
        return res;
    }
};

一个队列：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root == NULL) return res;
        q.push(root);
        q.push(NULL);//每一层结点结束以后都放一个NULL
        vector<int> le_val;
        
        while(!q.empty()){
            TreeNode* temNode = q.front();
            q.pop();
            if(temNode == NULL){//如果是NULL，说明一层已经遍历完成，同时，如果队列不为空，就再加一个NULL，作为下一层的结束标志
                res.push_back(le_val);
                le_val.clear();
                if(q.size()) q.push(NULL); 
            } else {//push进去下一层的结点
                le_val.push_back(temNode->val);
                if(temNode->left) q.push(temNode->left);
                if(temNode->right) q.push(temNode->right);
            }
        }
       return res; 
    }
};

递归的解决方案：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    void check(TreeNode* root, int depth){
        if(root == NULL) return ;
        if(res.size() == depth)
        {
            res.push_back(vector<int>());
        }
        res[depth].push_back(root->val);
        check(root->left, depth + 1);
        check(root->right, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        check(root, 0);
        return res;
    }
};

---