前言

代码随想录算法训练营day15

一、Leetcode 102.层序遍历

1.题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 (即逐层地，从左到右访问所有节点)。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1] 输出：[[1]]

示例 3：

输入：root = [] 输出：[]

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/binary-tree-level-order-traversal

2.解题思路

方法一：广度优先搜索

思路和算法

我们可以用广度优先搜索解决这个问题。

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用哈希表，维护一个以 level 为键，对应节点值组成的数组为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可。

考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？

我们可以用一种巧妙的方法修改广度优先搜索：

1. 首先根元素入队
2. 当队列不为空的时候
3.     求当前队列的长度 sisi
4.     依次从队列中取 sisi 个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 sisi 个元素。在上述过程中的第 ii 次迭代就得到了二叉树的第 ii 层的 sisi 个元素。

为什么这么做是对的呢？我们观察这个算法，可以归纳出这样的循环不变式：第 ii 次迭代前，队列中的所有元素就是第 ii 层的所有元素，并且按照从左向右的顺序排列。证明它的三条性质(你也可以把它理解成数学归纳法)：

1. 初始化：i=1i=1 的时候，队列里面只有 root，是唯一的层数为 11 的元素，因为只有一个元素，所以也显然满足「从左向右排列」；
2. 保持：如果 i=ki=k 时性质成立，即第 kk 轮中出队 sksk 的元素是第 kk 层的所有元素，并且顺序从左到右。因为对树进行广度优先搜索的时候由低 kk 层的点拓展出的点一定也只能是 k+1k+1 层的点，并且 k+1k+1 层的点只能由第 kk 层的点拓展到，所以由这 sksk 个点能拓展到下一层所有的 sk+1sk+1 个点。又因为队列的先进先出(FIFO)特性，既然第 kk 层的点的出队顺序是从左向右，那么第 k+1k+1 层也一定是从左向右。至此，我们已经可以通过数学归纳法证明循环不变式的正确性。
3. 终止：因为该循环不变式是正确的，所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此，我们证明了算法是正确的。

3.代码实现

```java class Solution { public List > levelOrder(TreeNode root) { List > ret = new ArrayList >(); if (root == null) { return ret; }

1. Queue<TreeNode> queue = new LinkedList<TreeNode>();
2.     queue.offer(root);
3.     while (!queue.isEmpty()) {
4.         List<Integer> level = new ArrayList<Integer>();
5.         int currentLevelSize = queue.size();
6. for (int i = 1; i <= currentLevelSize; ++i) {
7.             TreeNode node = queue.poll();
8.             level.add(node.val);
9. if (node.left != null) {
10.                 queue.offer(node.left);
11.             }
12. if (node.right != null) {
13.                 queue.offer(node.right);
14.             }
15.         }
16.         ret.add(level);
17.     }
18. 
19. return ret;
20. }

}

```

二、Leetcode 226.翻转二叉树

1.题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3] 输出：[2,3,1]

示例 3：

输入：root = [] 输出：[]

提示：

1. 树中节点数目范围在 [0, 100] 内
2. -100 <= Node.val <= 100

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/invert-binary-tree

2.解题思路

方法一：递归

这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 rootroot 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 rootroot 为根节点的整棵子树的翻转。

3.代码实现

```java class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }

```

三、Leetcode 101.对称二叉树

1.题目

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3] 输出：false

提示：

1. 树中节点数目在范围 [1, 1000] 内
2. -100 <= Node.val <= 100

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/symmetric-tree

2.解题思路

方法一：递归

思路和算法

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

fig1

因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

1. 它们的两个根结点具有相同的值
2. 每个树的右子树都与另一个树的左子树镜像对称

fig2

我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，pp 指针和 qq 指针一开始都指向这棵树的根，随后 pp 右移时，qq 左移，pp 左移时，qq 右移。每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称。

3.代码实现

```java class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); }

1. public boolean check(TreeNode p, TreeNode q) {
2. if (p == null && q == null) {
3. return true;
4.     }
5. if (p == null || q == null) {
6. return false;
7.     }
8. return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
9. }