本文主要是介绍代码随想录算法训练营第十五天 |层序遍历（10道），226.翻转二叉树，101.对称二叉树（待补充），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二叉树的层序遍历（已观看视频，10道题）
102.二叉树层序遍历（特别重要，是模板）
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
5、思路：
我们之前讲过了三篇关于二叉树的深度优先遍历的文章：
- 二叉树：前中后序递归法(opens new window)
- 二叉树：前中后序迭代法(opens new window)
- 二叉树：前中后序迭代方式统一写法(opens new window)
接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
使用队列实现二叉树广度优先遍历，动画如下：
这样就实现了层序从左到右遍历二叉树。
代码如下：这份代码也可以作为二叉树层序遍历的模板，打十个就靠它了。
- 时间复杂度: O(n)
- 空间复杂度: O(n)
class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {// 递归遍历checkFun01(root, 0);// 迭代遍历// checkFun02(root);return resList;}private void checkFun01(TreeNode root, int level) {if (root == null) {return;}level++;if (resList.size() < level) {// 当层级增加时，list的Item也增加，利用list的索引值进行层级界定List<Integer> item = new ArrayList<Integer>();resList.add(item);}resList.get(level - 1).add(root.val);checkFun01(root.left, level);checkFun01(root.right, level);}private void checkFun02(TreeNode root) {// 判断是否为空if (root == null) {return;}// 初始化队列Queue<TreeNode> queue = new LinkedList<>();// 加入根节点queue.add(root);// 开始循环while (!queue.isEmpty()) {// 定义一个list，存放当前层节点的值List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}size--;}resList.add(list);}}
}107.二叉树的层序遍历II
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
4、思路：
相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。
class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> res = new ArrayList<>();// 判断是否为空if (root == null) {return res;}// 初始化队列Queue<TreeNode> queue = new LinkedList<>();// 加入根节点queue.add(root);// 开始循环while (!queue.isEmpty()) {// 定义一个list，存放当前层节点的值List<Integer> list = new ArrayList<>();int size = queue.size();while (size > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}size--;}res.add(list);}// 反转List<List<Integer>> ans = new ArrayList<>();for (int i = res.size() - 1; i >= 0; i--) {ans.add(res.get(i));}return ans;}
}199.二叉树的右视图
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
4、思路：
层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return res;}queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}// 如果当前节点是最后一个节点，那么就将当前节点的值加入到结果集if (i == size - 1) {res.add(node.val);}}}return res;}
}637.二叉树的层平均值
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
4、思路：
本题就是层序遍历的时候把一层求个总和在取一个均值。
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> ans = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return ans;}queue.add(root);while (!queue.isEmpty()) {// 每一层的个数int size = queue.size();// 每一层的和Double sum = 0.0;for (int i = 0; i < size; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}ans.add(sum / size);}return ans;}
}429.N叉树的层序遍历
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[ [1], [3,2,4], [5,6] ]
4、思路：
这道题依旧是模板题，只不过一个节点有多个孩子了
class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> levelOrder(Node root) {if(root == null){return res;}Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> level = new ArrayList<>();for(int i = 0;i < size;i++){Node node = queue.poll();level.add(node.val);for(Node child : node.children){queue.add(child);}}res.add(level);}return res;}
}515.在每个树行中找最大值
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
您需要在二叉树的每一行中找到最大的值。
4、思路：
层序遍历，取每一层的最大值
class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return res;}queue.add(root);while (!queue.isEmpty()) {int size = queue.size();// 定义最大值int max = Integer.MIN_VALUE;for (int i = 0; i < size; i++) {TreeNode node = queue.poll();// 取每一层的最大值max = Math.max(max, node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}res.add(max);}return res;}
}116.填充每个节点的下一个右侧节点指针（待补充）
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
4、思路：
本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了
117.填充每个节点的下一个右侧节点指针II（待补充）
104.二叉树的最大深度（待补充）
111.二叉树的最小深度（待补充）
226.翻转二叉树
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
翻转一棵二叉树。
4、视频链接：
听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树_哔哩哔哩_bilibili
5、思路：
我们之前介绍的都是各种方式遍历二叉树，这次要翻转了，感觉还是有点懵逼。
这得怎么翻转呢？
如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：
可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了
那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！
#递归法
对于二叉树的递归法的前中后序遍历，已经在二叉树：前中后序递归遍历(opens new window)详细讲解了。
我们下文以前序遍历为例，通过动画来看一下翻转的过程:
我们来看一下递归三部曲：
- 确定递归函数的参数和返回值
参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。
返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*。
TreeNode* invertTree(TreeNode* root)- 确定终止条件
当前节点为空的时候，就返回
if (root == NULL) return root;- 确定单层递归的逻辑
因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
swap(root->left, root->right);
invertTree(root->left);
invertTree(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;}
};#迭代法
#深度优先遍历
二叉树：听说递归能做的，栈也能做！(opens new window)中给出了前中后序迭代方式的写法，所以本题可以很轻松的写出如下迭代法的代码：
C++代码迭代法（前序遍历）
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;stack<TreeNode*> st;st.push(root);while(!st.empty()) {TreeNode* node = st.top(); // 中st.pop();swap(node->left, node->right);if(node->right) st.push(node->right); // 右if(node->left) st.push(node->left); // 左}return root;}
};如果这个代码看不懂的话可以再回顾一下二叉树：听说递归能做的，栈也能做！(opens new window)。
我们在二叉树：前中后序迭代方式的统一写法(opens new window)中介绍了统一的写法，所以，本题也只需将文中的代码少做修改便可。
C++代码如下迭代法（前序遍历）
class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right) st.push(node->right); // 右if (node->left) st.push(node->left); // 左st.push(node); // 中st.push(NULL);} else {st.pop();node = st.top();st.pop();swap(node->left, node->right); // 节点处理逻辑}}return root;}
};如果上面这个代码看不懂，回顾一下文章二叉树：前中后序迭代方式的统一写法(opens new window)。
#广度优先遍历
也就是层序遍历，层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍，代码如下：
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();swap(node->left, node->right); // 节点处理if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return root;}
};如果对以上代码不理解，或者不清楚二叉树的层序遍历，可以看这篇二叉树：层序遍历登场！
6、总结：
总结
针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历。
二叉树解题的大忌就是自己稀里糊涂的过了（因为这道题相对简单），但是也不知道自己是怎么遍历的。
这也是造成了二叉树的题目“一看就会，一写就废”的原因。
针对翻转二叉树，我给出了一种递归，三种迭代（两种模拟深度优先遍历，一种层序遍历）的写法，都是之前我们讲过的写法，融汇贯通一下而已。
递归遍历
class Solution {/*** 递归遍历* 前后序遍历都可以* 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）*/public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}invertTree(root.left);invertTree(root.right);// 后序遍历，如果是前序遍历，把swap放inver上面swapChildren(root);return root;}private void swapChildren(TreeNode root) {TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}迭代遍历
class Solution {/*** 迭代遍历*/public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}Deque<TreeNode> deque = new LinkedList<>();deque.add(root);while (!deque.isEmpty()) {int size = deque.size();for (int i = 0; i < size; i++) {TreeNode node = deque.poll();swapChildren(node);if (node.left != null) {deque.add(node.left);}if (node.right != null) {deque.add(node.right);}}}return root;}private void swapChildren(TreeNode root) {TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}101、对称二叉树
1、题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、文章讲解：代码随想录
3、题目：
给定一个二叉树，检查它是否是镜像对称的。
4、思路：
首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
那么如何比较呢？
比较的是两个子树的里侧和外侧的元素是否相等。如图所示：
那么遍历的顺序应该是什么样的呢？
本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。
说到这大家可能感觉我有点啰嗦，哪有这么多道理，上来就干就完事了。别急，我说的这些在下面的代码讲解中都有身影。
那么我们先来看看递归法的代码应该怎么写。
#递归法
递归三部曲
- 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下：
bool compare(TreeNode* left, TreeNode* right)- 确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
- 左节点为空，右节点不为空，不对称，return false
- 左不为空，右为空，不对称 return false
- 左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
- 左右都不为空，比较节点数值，不相同就return false
此时左右节点不为空，且数值也不相同的情况我们也处理了。
代码如下：
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里我没有使用else注意上面最后一种情况，我没有使用else，而是else if， 因为我们把以上情况都排除之后，剩下的就是 左右节点都不为空，且数值相同的情况。
- 确定单层递归的逻辑
此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
- 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
- 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
- 如果左右都对称就返回true ，有一侧不对称就返回false 。
代码如下：
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
bool isSame = outside && inside; // 左子树：中、 右子树：中（逻辑处理）
return isSame;如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。
最后递归的C++整体代码如下：
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {// 首先排除空节点的情况if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;// 排除了空节点，再排除数值不相同的情况else if (left->val != right->val) return false;// 此时就是：左右节点都不为空，且数值相同的情况// 此时才做递归，做下一层的判断bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左bool isSame = outside && inside; // 左子树：中、 右子树：中 （逻辑处理）return isSame;}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return compare(root->left, root->right);}
};我给出的代码并不简洁，但是把每一步判断的逻辑都清楚的描绘出来了。
如果上来就看网上各种简洁的代码，看起来真的很简单，但是很多逻辑都掩盖掉了，而题解可能也没有把掩盖掉的逻辑说清楚。
盲目的照着抄，结果就是：发现这是一道“简单题”，稀里糊涂的就过了，但是真正的每一步判断逻辑未必想到清楚。
当然我可以把如上代码整理如下：
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;else if (left->val != right->val) return false;else return compare(left->left, right->right) && compare(left->right, right->left);}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return compare(root->left, root->right);}
};这个代码就很简洁了，但隐藏了很多逻辑，条理不清晰，而且递归三部曲，在这里完全体现不出来。
所以建议大家做题的时候，一定要想清楚逻辑，每一步做什么。把题目所有情况想到位，相应的代码写出来之后，再去追求简洁代码的效果。
#迭代法
这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。
这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）
#使用队列
通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，如动画所示：
如下的条件判断和递归的逻辑是一样的。
代码如下：
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;queue<TreeNode*> que;que.push(root->left); // 将左子树头结点加入队列que.push(root->right); // 将右子树头结点加入队列while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转TreeNode* leftNode = que.front(); que.pop();TreeNode* rightNode = que.front(); que.pop();if (!leftNode && !rightNode) { // 左节点为空、右节点为空，此时说明是对称的continue;}// 左右一个节点不为空，或者都不为空但数值不相同，返回falseif ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;}que.push(leftNode->left); // 加入左节点左孩子que.push(rightNode->right); // 加入右节点右孩子que.push(leftNode->right); // 加入左节点右孩子que.push(rightNode->left); // 加入右节点左孩子}return true;}
};#使用栈
细心的话，其实可以发现，这个迭代法，其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。
只要把队列原封不动的改成栈就可以了，我下面也给出了代码。
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;stack<TreeNode*> st; // 这里改成了栈st.push(root->left);st.push(root->right);while (!st.empty()) {TreeNode* leftNode = st.top(); st.pop();TreeNode* rightNode = st.top(); st.pop();if (!leftNode && !rightNode) {continue;}if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;}st.push(leftNode->left);st.push(rightNode->right);st.push(leftNode->right);st.push(rightNode->left);}return true;}
};#总结
这次我们又深度剖析了一道二叉树的“简单题”，大家会发现，真正的把题目搞清楚其实并不简单，leetcode上accept了和真正掌握了还是有距离的。
我们介绍了递归法和迭代法，递归依然通过递归三部曲来解决了这道题目，如果只看精简的代码根本看不出来递归三部曲是如何解题的。
在迭代法中我们使用了队列，需要注意的是这不是层序遍历，而且仅仅通过一个容器来成对的存放我们要比较的元素，知道这一本质之后就发现，用队列，用栈，甚至用数组，都是可以的。
如果已经做过这道题目的同学，读完文章可以再去看看这道题目，思考一下，会有不一样的发现！
class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left, root.right);}private boolean compare(TreeNode left, TreeNode right) {if (left == null && right != null) {return false;}if (left != null && right == null) {return false;}if (left == null && right == null) {return true;}if (left.val != right.val) {return false;}// 比较外侧boolean compareOutside = compare(left.left, right.right);// 比较内侧boolean compareInside = compare(left.right, right.left);return compareOutside && compareInside;}
}class Solution {// 使用普通队列public boolean isSymmetric(TreeNode root) {Queue<TreeNode> deque = new LinkedList<>();deque.offer(root.left);deque.offer(root.right);while (!deque.isEmpty()) {TreeNode leftNode = deque.poll();TreeNode rightNode = deque.poll();if (leftNode == null && rightNode == null) {continue;}
// if (leftNode == null && rightNode != null) {
// return false;
// }
// if (leftNode != null && rightNode == null) {
// return false;
// }
// if (leftNode.val != rightNode.val) {
// return false;
// }// 以上三个判断条件合并if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {return false;}// 这里顺序与使用Deque不同deque.offer(leftNode.left);deque.offer(rightNode.right);deque.offer(leftNode.right);deque.offer(rightNode.left);}return true;}
}这篇关于代码随想录算法训练营第十五天 |层序遍历（10道），226.翻转二叉树，101.对称二叉树（待补充）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
