题目描述：
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ 9 20
/ 15 7
返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
思路：
笔试时采用了queue的遍历方式，但用的是一维数组存的，感觉有点别扭。
网上的queue解法模板
/** * 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;//保存结果 TreeNode * first =root; if(!first) return res; queue<TreeNode *> q; q.push(first); while(!q.empty()) { int count = q.size(); vector<int> t; while(count!=0) { TreeNode *p=q.front(); q.pop(); t.push_back(p->val); if(p->left) q.push(p->left); if(p->right) q.push(p->right); count--; } res.push_back(t); } return res; } };
第二种采用先序遍历递归，个人感觉代码更加简洁，但稍微难理解点。复杂度都是O（n）
depth变量记录当前在第几层（从0开始），进入下层时depth + 1；depth >= vector.size()说明这一层还没来过，这是第一次来，所以得扩容咯；/** * 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 pre(TreeNode *root,int depth, vector<vector<int>> &res) { if(root==NULL) return ; if(depth>=res.size()) res.push_back(vector<int>{}); res[depth].push_back(root->val); pre(root->left,depth+1,res); pre(root->right,depth+1,res); } vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans; pre(root,0,ans); return ans; } };
原文：https://www.cnblogs.com/-xinxin/p/10741800.html