剑指offer一刷：搜索与回溯算法
剑指 Offer 32 - I. 从上到下打印二叉树
难度：中等
方法一：层序遍历 BFS
题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。
BFS 通常借助队列的先入先出特性来实现。
算法流程：
- 特例处理：当树的根节点为空，则直接返回空列表 []；
- 初始化：打印结果列表 res = []，包含根节点的队列 queue = [root]；
- BFS 循环：当队列 queue 为空时跳出；
- 出队：队首元素出队，记为 node；
- 打印：将 node.val 添加至列表 tmp 尾部；
- 添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue；
- 返回值：返回打印结果列表 res 即可。
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
Queue queue = new LinkedList<>(){{ add(root); }};
ArrayList ans = new ArrayList<>();
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
ans.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9ab39g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 时间复杂度：O(N)，空间复杂度：O(N)。
剑指 Offer 32 - II. 从上到下打印二叉树 II
难度：简单
方法一：层序遍历 BFS
在 I 的基础上，将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
算法流程：
- 特例处理：当根节点为空，则返回空列表 []；
- 初始化：打印结果列表 res = []，包含根节点的队列 queue = [root]；
- BFS 循环：当队列 queue 为空时跳出；
- 新建一个临时列表 tmp，用于存储当前层打印结果；
- 当前层打印循环：循环次数为当前层节点数（即队列 queue 长度）；
- 出队：队首元素出队，记为 node；
- 打印：将 node.val 添加至 tmp 尾部；
- 添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue；
- 出队：队首元素出队，记为 node；
- 将当前层结果 tmp 添加入 res。
- 新建一个临时列表 tmp，用于存储当前层打印结果；
- 返回值：返回打印结果列表 res 即可。
class Solution {
public List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5v22om/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 时间复杂度：O(N)，空间复杂度：O(N)。
其中的 int i = queue.size(); 用的很妙，学习学习。
剑指 Offer 32 - III. 从上到下打印二叉树 III
难度：中等
方法一：层序遍历 + 双端队列
算法流程：
- 特例处理：当树的根节点为空，则直接返回空列表 []；
- 初始化：打印结果空列表 res，包含根节点的双端队列 deque；
- BFS 循环：当 deque 为空时跳出；
- 新建列表 tmp，用于临时存储当前层打印结果；
- 当前层打印循环：循环次数为当前层节点数（即 deque 长度）；
- 出队：队首元素出队，记为 node；
- 打印：若为奇数层，将 node.val 添加至 tmp 尾部；否则，添加至 tmp 头部；
- 添加子节点：若 node 的左（右）子节点不为空，则加入 deque；
- 出队：队首元素出队，记为 node；
- 将当前层结果 tmp 转化为 list 并添加入 res；
- 新建列表 tmp，用于临时存储当前层打印结果；
- 返回值： 返回打印结果列表 res 即可；
class Solution {
public List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
LinkedList tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if(res.size() % 2 == 0) tmp.addLast(node.val);
else tmp.addFirst(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vve57/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 时间复杂度：O(N)，空间复杂度：O(N)。
方法二：层序遍历 + 双端队列（奇偶逻辑分离）
- 方法一代码简短、容易实现；但需要判断每个节点的所在层奇偶性，即冗余了 N 次判断。
- 通过将奇偶层逻辑拆分，可以消除冗余的判断。
算法流程：
- BFS 循环：循环打印奇 / 偶数层，当 deque 为空时跳出；
- 打印奇数层：从左向右打印，先左后右加入下层节点；
- 若 deque 为空，说明向下无偶数层，则跳出；
- 打印偶数层：从右向左打印，先右后左加入下层节点；
class Solution {
public List> levelOrder(TreeNode root) {
Deque deque = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) deque.add(root);
while(!deque.isEmpty()) {
// 打印奇数层
List tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从左向右打印
TreeNode node = deque.removeFirst();
tmp.add(node.val);
// 先左后右加入下层节点
if(node.left != null) deque.addLast(node.left);
if(node.right != null) deque.addLast(node.right);
}
res.add(tmp);
if(deque.isEmpty()) break; // 若为空则提前跳出
// 打印偶数层
tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从右向左打印
TreeNode node = deque.removeLast();
tmp.add(node.val);
// 先右后左加入下层节点
if(node.right != null) deque.addFirst(node.right);
if(node.left != null) deque.addFirst(node.left);
}
res.add(tmp);
}
return res;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vve57/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 时间复杂度：O(N)，空间复杂度：O(N)。
方法三：层序遍历 + 倒序
- 偶数层倒序：若 res 的长度为奇数，说明当前是偶数层，则对 tmp 执行倒序操作。
class Solution {
public List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
if(res.size() % 2 == 1) Collections.reverse(tmp);
res.add(tmp);
}
return res;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vve57/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 时间复杂度：O(N)，空间复杂度：O(N)。
剑指 Offer 26. 树的子结构
难度：中等
方法一：先序遍历 + 包含判断
若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：
- 先序遍历树 A 中的每个节点 nA；（对应函数 isSubStructure(A, B) ）
- 判断树 A 中以 nA 为根节点的子树是否包含树 B。（对应函数 recur(A, B) ）
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if(B == null) return true;
if(A == null || A.val != B.val) return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dsbng/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。时间复杂度：O(MN)，空间复杂度：O(M)，其中 M, N 分别为树 A 和 树 B 的节点数量。
剑指 Offer 27. 二叉树的镜像
难度：简单
（注意是对原树镜像，不是输出一个新的镜像，一开始做错了）
方法一：递归法
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
TreeNode tmp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(tmp);
return root;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59slxe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。时间复杂度：O(N)，空间复杂度：O(N)。
方法二：辅助栈（或队列）
算法流程：
- 特例处理：当 root 为空时，直接返回 null；
- 初始化：栈（或队列），本文用栈，并加入根节点 root。
- 循环交换：当栈 stack 为空时跳出；
- 出栈：记为 node；
- 添加子节点：将 node 左和右子节点入栈；
- 交换：交换 node 的左 / 右子节点。
- 返回值：返回根节点 root。
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
Stack stack = new Stack<>() {{ add(root); }};
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
}
return root;
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59slxe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 时间复杂度：O(N)，空间复杂度：O(N)。
剑指 Offer 28. 对称的二叉树
难度：简单
方法一：递归法
对称二叉树定义：对于树中任意两个对称节点 L 和 R，一定有：
- L.val = R.val：即此两对称节点值相等。
- L.left.val = R.right.val：即 L 的左子节点和 R 的右子节点对称；
- L.right.val = R.left.val：即 L 的右子节点和 R 的左子节点对称。
根据以上规律，考虑从顶至底递归，判断每对左右节点是否对称，从而判断树是否为对称二叉树。
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if(L == null && R == null) return true;
if(L == null || R == null || L.val != R.val) return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}
}
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5d1zmj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。时间复杂度：O(N)，空间复杂度：O(N)。