leetcode剑指32-II 二叉树层序遍历

题目；https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/zi-jie-ti-ku-jian-32-ii-jian-dan-cong-shang-dao-xi/

思路：广度优先搜索 利用队列 （先进先出） 1. 先判断树是否为空，为空就返回空； 2. 不为空将根节点入队列，判断队列是否为空，不为空就循环 3. 计算队列的长度（得到当前层的节点数），遍历当前层的每个节点， 将队首元素出队列，将值抛进一个一维数组里面，将该结点的下一层元素都加队列（左子树、右子 树 入队列）遍历完当前层的节点后。将一维数组入二维数组，将一维数组清空，为下一层节点遍历做准备。 4. 直到队列为空，循环结束。

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*>que; vector<vector<int>> vec; vector<int>A; que.push(root); if(root==NULL) return vec; while (!que.empty()) { int len = que.size(); for (int i = 0; i < len; i++) { TreeNode*node = que.front(); que.pop(); if (node->left)que.push(node->left); if (node->right)que.push(node->right); A.push_back(node->val); } vec.push_back(A); A.clear(); } return vec; } };

思路二：深度优先算法（递归实现

函数参数：节点，数组（引用方式），level用于记录当前结点的层数 函数返回值：无返回值 递归终止的条件：无节点（节点为空） 单层逻辑：

判断节点是否为空，为空就返回

判断树的层数是否比数组的维数大，比数组的维数大在数组里面插入 空；

将某层的节点数压入某维数的数组

递归调用左子树 递归调用右子树

注意：

level参数表示深度，把节点加到对应深度的位置就行

数组为何采用引用： 用引用作为函数的参数时，其效果和用指针作为函数参数的效果相当。当调用函数时，函数中的形参就会被当成实参变量或对象的一个别名来使用，也就是说此时函数中对形参的各种操作实际上是对实参本身进行操作，而非简单的将实参变量或对象的值拷贝给形参。

vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>>res; dfs(root, res, 0); return res; } void dfs(TreeNode* root, vector<vector<int>>& res, int level) { if (root == NULL) return; if (level >= res.size()) res.push_back(vector<int>()); res[level].push_back(root->val); //将节点加入对应的深度位置 dfs(root->left, res, level + 1); dfs(root->right, res, level + 1); }