原题地址：https://leetcode.com/problems/binary-tree-level-order-traversal/description/
题目描述
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree[3,9,20,null,null,15,7]，
return its zigzag level order traversal as:
[ [3], [9,20], [15,7] ]
即由上到下由左到右把每一层的节点值放在一个vector<int>里，最后返回一个大的vector<vector<int>>
解题思路
和上一题很像，用深度优先遍历，在深度优先里递归左子节点再递归右子节点。创建一个变量deepest保存目前最大深度，同时遍历的时候记录当前深度，如果当前深度比最大深度更大，就更新最大深度，同时创建一个新的vector<int>放到vector<vector<int>>末尾，并把当前节点的值放入那个新的vector<int>的末尾。
代码
/**
* 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:
int deepest = 0;
vector<vector<int> > result;
void DFS(TreeNode* root,int current_level){
if(root==NULL){
return ;
}
current_level++;
if(current_level > deepest){
deepest=current_level;
vector<int> temp;
result.push_back(temp);
}
result[current_level-1].push_back(root->val);
DFS(root->left,current_level);
DFS(root->right,current_level);
}
vector<vector<int>> levelOrder(TreeNode* root) {
DFS(root,0);
return result;
}
};
TIM截图20170918151604.png
