代码随想录笔记|C++数据结构与算法学习笔记-二叉树(二)|二叉树层序遍历、226.翻转二叉树

本文主要是介绍代码随想录笔记|C++数据结构与算法学习笔记-二叉树(二)|二叉树层序遍历、226.翻转二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树层序遍历

文章链接：二叉树层序遍历

视频链接：讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

如何去层序遍历二叉树呢？如果依赖二叉树这种结构本身，无法层序保存结点的。我们需要借助一个队列来帮我们保存每一层里面遍历过的元素

队列模拟过程

他本质上是图论的广度优先搜索，也是依赖队列来去实现。

对于一个二叉树

​ A

/
B C
/ \ / \
D E F G

首先一个根结点A加入到队列，并且要记录我们的队列大小size = 1，然后我们把当前层的元素A弹出来加入到结果数组里

然后我们把第二层数据B、C加入到队列里，此时的size = 2，这个队列大小就记录着第二层的元素个数就是2，接下来我们遍历这个队列是只弹出2个元素，因为队列中的元素是变化的，所以我们一定要记录好该层的元素。

所以我们把B弹出，现在我们需要把下一层的元素加入到队列，所以当前队列的元素是[C D E]，如果没有size来记录每一层元素的个数，我们如何知道队列中的元素哪些是第二层哪些是第三层呢？刚好之前我们已经记录了第二层大小是2。所以现在我们弹出C。

然后把C的左右孩子加入到队列也就是[D E F G]，size = 4.就表示了我们的第三层有4个结点。然后我们把DEFG弹出。

那么按刚才的规则把DEFG都弹出之后，我们再一次记录栈的size。这个size就是第四层的结点数，在本题中很显然，没有第四层，所以栈也是空的，我们随后跳出循环即可。

伪代码实现

queue<TreeNode*> que;
if(root != NULL) que.push(root);//root不为空就把根结点加入到队列中
while(!que.empty)//如果队列中没有元素了，也就是说层序遍历没有元素添加到队列中了，层序遍历终止
{  size = que.size();vector<int> vec;//每层用一个一维数组保存while (size--)	//这里的循环条件千万不能写成que.size()因为队列的长度在不断变化{note = que.front(); que.pop();vec.push_back(node->val);//记录完本层结点后将结点的左右孩子加入到队列中if (node->left)	que.push(node->left);if (node->right) que.push(node->right);}
}

C++实现

迭代法：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

递归法：

class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

226.翻转二叉树

力扣题目链接

文章链接：226.翻转二叉树

视频链接：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树

遍历顺序的重要性

一定要确认好遍历顺序。这道题目用前序和后序是最合适的，用中序遍历不太方便。

前序和中序遍历的代码实现

如果用递归遍历的话，一定要想好递归三部曲

• 确定递归函数的返回值和参数

​ 函数返回值是结点的定义，参数后面慢慢确定都无所谓

FreeNode* invertTree(TreeNode* root)

• 确定终止条件

​ 什么时候终止遍历呢，就是碰到空结点的时候

if (root == NULL) return root;

• 处理逻辑

​ 先写前序遍历：中左右，中间就是我们要处理的地方，处理的逻辑就是交换这个结点的两个孩子。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

​ 然后是后序遍历：左右中

invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);

C++ 代码实现

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right);  // 中invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}
};

为什么不用中序遍历

左中右的遍历顺序，会导致，左子树被反复处理，右子树没被处理。

具体过程请参看视频：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树

此时的代码应该写成

invertTree(root->left);
swap(root->left, root->right);
invertTree(root->left);	//为什么这里还处理左子树呢，因为现在的左子树其实是之前的右子树！

二叉树阶段性总结Part1

先做个标记，总结以后再写，感觉好难😭

这篇关于代码随想录笔记|C++数据结构与算法学习笔记-二叉树(二)|二叉树层序遍历、226.翻转二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---