二叉树层序遍历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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

二、迭代方法

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);
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30