LeetCode二叉树层序遍历I

文章目录

• • • • LeetCode二叉树层序遍历I
      • • 一、递归方法
        • 二、迭代方法

一、递归方法

1. 首先判断当前root结点是否为空（if(!root)）：如果为空，则直接返回（整个递归的出口）
2. 判断二维数组result的大小与level的大小关系（判定有没有属于自己这一层的网格）
   1. 如果没有，则自己创建一个网格result.push_back(vector());
3. 将该结点的值放入对应网格的最后，即result[level-1].push_back(p->val);
4. 在依次递归遍历该结点的左节点和右节点
   1. 左节点：Traversal(root->left, level + 1, result);
   2. 右节点：Traversal(root->right, level + 1, result);

代码如下：

#include
#include
using namespace std;struct TreeNode {TreeNode* left;TreeNode* right;int val;TreeNode(int x) :val(x), left(nullptr), right(nullptr) {};
};class Binary_Tree_Level_Order_Traversal_recursion {vector>LevelOrder(TreeNode* root) {vector> result;Traversal(root, 1, result);return result;}void Traversal(TreeNode* root, int level, vector>& result) {if (!root) return; // 如果root指针为空（0）则返回，函数退出if (level > result.size())result.push_back(vector());result[level - 1].push_back(root->val);Traversal(root->left, level + 1, result);Traversal(root->right, level + 1, result);}
};

二、迭代方法

1. 利用两个队列的出入队和互换实现层序的遍历
2. 创建两个队列queue current, next;
3. 首先将根节点root存入current队列之中
4. 当current队列不为空，进入第1个while循环：while (!current.empty())
   1. 创建用于保存该层数据的一维向量vector Level;
   2. 进入第2个循环：while (!current.empty())，循环内操作与前序遍历很类似
      1. 将队首元素出队，即current.pop()
      2. 保存出队元素的值，即level.push_back(p->val);
      3. 分别将左右孩子的指针（如果存在的话）存到next队列中，用来下一次的遍历
         1. 左孩子：if (p->left) next.push(p->left);
         2. 右孩子：if (p->right) next.push(p->right);
   3. 将level的值存进result中
   4. 将current的内容与next队列互换即可准备下一层的遍历操作

代码如下：

#include
#include
#include
using namespace std;class Binary_Tree_Level_Order_Traversal_iteration {vector> LevelOrder(TreeNode* root) {vector> result;Traversal(root, 1, result);return result;}void Traversal(TreeNode* root, int level, vector>& result) {queue current, next;current.push(root);if (!root) return;while (!current.empty()) {vector Level;while (!current.empty()) {TreeNode* p = current.front();current.pop();Level.push_back(p->val);if (p->left) next.push(p->left);if (p->right) next.push(p->right);}result.push_back(Level);swap(current, next);}}
};