102. Binary Tree Level Order Traversal

题意

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

题解

很明显，要采用层序遍历。采用队列存储数据。把每一层的节点都添加到同一个数组中即可，问题的关键在于遍历同一层节点前，必须事先算出同一层的节点个数有多少（即队列已有元素个数），因为 BFS 用的是队列来实现的，遍历过程中会不断把左右子节点入队。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        //层序遍历
        
        if(root==NULL) return {};
        queue q;
        q.push(root);
        vector> res;
        while(!q.empty()){
            int size = q.size();
            vector level;
            for(int i=0; ival);
                if(temp -> left !=NULL) q.push(temp->left);
                if(temp -> right != NULL) q.push(temp -> right);                
            }
            res.push_back(level);  
        }
        return res;
        
    }
};

DFS：

         DFS 可以用递归来实现，其实只要在递归函数上加上一个「层」的变量即可，只要节点属于这一层，则把这个节点放入相当层的数组里，代码如下：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector>res;
        DFS(res, root, 0);
        return res;
    }
    
    void DFS(vector>& res, TreeNode* root, int level){
        if(!root) return;
        if(level == res.size()) res.push_back(vector());
        res[level].push_back(root->val);
        DFS(res, root->left, level + 1);
        DFS(res, root->right, level + 1);
    }
};