LeetCode 102. 二叉树的层次遍历

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

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

3
/
9 20
/
15 7
返回其层次遍历结果：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal

递归：

/**
 * 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:
    void process(TreeNode* root,int depth,vector<vector<int>> &ans)
    {

        if(depth >= ans.size())
            ans.push_back(vector<int> {});

        ans[depth].push_back(root->val);
        if(root->left) process(root->left,depth+1,ans);
        if(root->right) process(root->right,depth+1,ans);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;

        if(root)
            process(root,0,ans);
        return ans;
    }   
};

非递归：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrder(TreeNode* root) {
13         
14         vector<vector<int>> ans;
15         if(!root) return ans;
16 
17         queue<TreeNode*> Q;
18         TreeNode* temp;
19         Q.push(root);
20         while (!Q.empty()){
21             vector<int> ress;
22             int n = Q.size();
23             for(int i = 0; i < n; i++) {
24                 temp = Q.front();
25                 ress.push_back(temp->val);
26                 Q.pop();
27                 if(temp->left)
28                     Q.push(temp->left);
29                 if(temp->right)
30                     Q.push(temp->right);
31             }
32             ans.push_back(ress);
33         }
34         return ans;
35     }
36 };