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

示例：
二叉树：[3,9,20,null,null,15,7],

3

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

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

层序遍历很好理解就是一层层遍历。

第一种方法——递归：先准备一个全局的vector<vector< int >>容器v用以存结构，函数里先判断root是否为空，如果为空就直接把空的v返回，如果不为空，就把root传入dfs里，同时要传一个层数u，我们为了符合数组的存储方式层数我们从0开始。进入dfs，先判断root是否为空，如果为空就直接结束程序，如果不为空则判断一下当前v的size是否小于u+1，如果小于我们就创建一个vector容器插入v中，然后我们通过v[u].push_back()来插入当前root的val值，再把root的left和right分别送入下一次的dfs递归中，此时我们传的层数为u+1。当所有递归结束后返回v即可。

/*** 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<vector<int>>v;vector<vector<int>> levelOrder(TreeNode* root) {   if(!root)return v;vector<int>v1;v.assign(1, v1);dfs(root,0);return v;}void dfs(TreeNode* root, int u){if (!root)return;else{if(v.size()<u+1){vector<int>v1;v.push_back(v1);}v[u].push_back(root->val);dfs(root->left, u + 1);dfs(root->right, u + 1);}}
};

第二种方法——迭代：因为迭代是在一个函数里进行的，所以可以把全局函数vector<vector< int>>v设置在函数开头，当然也可以继续全局函数。先判断root是否为空，如果为空就返回空的v给它，如果不为空，那我们先准备一个queue容器que来存节点，先把root存入que中，然后开始while遍历，只要que不为空就一直遍历，每次遍历先拿一个数len存que的size，len就是当前层的节点数，这也决定了下面for循环的次数，再准备一个vector容器v1来存这一层节点的val值，然后开始for循环，循环len次，先把当前队列的头结点的val值存入v1中，然后把队列头结点的左子节点和右子节点存入que中，再把队头元素出队，for结束后把v1插入v中。一切遍历结束后返回v即可。

/*** 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<vector<int>> levelOrder(TreeNode* root) {   vector<vector<int>>v;if(!root)return v;queue<TreeNode*>que;que.push(root);while(que.size()){int len=que.size();vector<int>v1;for(int i=0;i<len;i++){v1.push_back(que.front()->val);if(que.front()->left)que.push(que.front()->left);if(que.front()->right)que.push(que.front()->right);que.pop();}v.push_back(v1);}return v;}
};

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1：

输入：
3
/
9 20
/
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

通过上面层序遍历的方法先得到各层的节点数，然后就正常的求平均值就是。

/*** 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<vector<int>>v;vector<double> averageOfLevels(TreeNode* root) {vector<double>nums;if(!root)return nums;dfs(root,0);double sum=0;int n=v.size();for(int i=0;i<n;i++){for(int j=0;j<v[i].size();j++){sum+=v[i][j];}nums.push_back(sum/v[i].size());sum=0;}return nums;}void dfs(TreeNode* root,int u){if(!root)return;else{if(v.size()<u+1){vector<int>v1;v.push_back(v1);}v[u].push_back(root->val);dfs(root->left,u+1);dfs(root->right,u+1);}}
};

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

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

​ 3

/
9 20
/
15 7
返回锯齿形层序遍历如下：

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

用上面求层序遍历的方法求完各层节点数，然后把奇数层的节点全都改成逆序就行（偷鸡法）

/*** 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<vector<int>>v;vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(!root)return v;dfs(root,0);int n=v.size();for(int i=1;i<n;i+=2){int m=v[i].size();int k=m-1;for(int j=0;j<m/2;j++){swap(v[i][j],v[i][k]);k--;}}return v;}void dfs(TreeNode* root, int u){if (!root)return;if (v.size() < u + 1){vector<int>v1;v.push_back(v1);}v[u].push_back(root->val);dfs(root->left, u + 1);dfs(root->right, u + 1);}
};

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

用上面求层序遍历的方法求完各层节点数，然后返回最后一层的的第一个数就行。

/*** 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<vector<int>>v;int findBottomLeftValue(TreeNode* root) {if(!root)return NULL;dfs(root,0);int n=v.size()-1;return v[n][0];}void dfs(TreeNode*root,int u){if(!root)return;if(v.size()<u+1){vector<int>v1;v.push_back(v1);}v[u].push_back(root->val);dfs(root->left,u+1);dfs(root->right,u+1);}
};

简单一点的方法：用一个queue容器que来存节点，准备一个数num_left来存每层最左边的数。先把root存入que中，然后开始while循环，只要que里还有元素就继续循环，先把当前队列的头元素的val值赋给num_left，因为队头元素就是每层的最左边的节点，再准备一个值len存当前队列的节点数，这代表这一层的节点数，也是下面for循环的结束条件。然后进入for循环，每次把当前队头元素的左子节点和右子节点传入队列，然后弹出队头元素（这时前面的len作用就体现出来了，循环len次，每次弹出队头元素，这样循环完后上一层的节点就全都消失，取之而代的是下一层的节点，队头元素就是最左边的节点）。当while结束后返回num_left。

/*** 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:int findBottomLeftValue(TreeNode* root) {if(!root)return NULL;queue<TreeNode*>que;int num_left;que.push(root);while(que.size()){int len=que.size();num_left=que.front()->val;for(int i=0;i<len;i++){if(que.front()->left)que.push(que.front()->left);if(que.front()->right)que.push(que.front()->right);que.pop();}}return num_left;}
};