刷穿剑指offer-Day23-树II 树的深度优先搜索!
昨日回顾
昨天我们学习了树的一些基础名词与分类，很多人想问，为什么很多公司的手撕算法环节都会选择树这个数据类型来考察面试者呢？
因为树中包含的知识太多了。我们在昨天介绍的树的前中后续遍历中，涉及到递归和迭代两种方式，单单这些就考察了我们对递归、栈、链表知识。更别说之前介绍过树的逐层遍历（广度优先搜索），以及之后要介绍的深度优先搜索。
说了这么多，只是为了再次强调树这个知识点的重要性。那么就要提问了，昨天留的94和145题树的中序和后续遍历，大家是否用两种方法完成了呢？我猜基本都没有。前序和中序在迭代的写法中几乎没有差异，然而后续遍历却略显复杂， 开篇先简单带着大家回顾下树的后续遍历知识吧。
145.二叉树的后序遍历
难度：简单
题目：
给定一个二叉树，返回它的 后序 遍历。
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
示例：
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
分析
对于递归的代码前中后序遍历，只需要修改val添加的位置即可。
但对于迭代的操作，则后续遍历稍显麻烦。
因为左 -> 右 -> 中 的访问过程中如果没有控制好右侧节点的链表指向，可能会造成死循环的问题。
解决问题的关键，当遍历到右节点为空的状态时，需要记录他的pre节点，避免造成栈与链表的循环访问即可。
递归解题：
Python:
class Solution:
def postorderTraversal(self, root):
ret = []
def dfs(tree):
if not tree:
return
dfs(tree.left)
dfs(tree.right)
ret.append(tree.val)
dfs(root)
return ret
Java:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
dfs(root, ret);
return ret;
}
private void dfs(TreeNode tree, List<Integer> ret){
if (tree == null){
return;
}
dfs(tree.left, ret);
dfs(tree.right, ret);
ret.add(tree.val);
}
}
迭代解题
Python:
class Solution:
def postorderTraversal(self, root):
ret, stack = [], []
cur, pre = root, None
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if not cur.right or cur.right == pre:
ret.append(cur.val)
pre = cur
cur = None
else:
stack.append(cur)
cur = cur.right
return ret
Java:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
if (cur.right == null || cur.right == pre){
ret.add(cur.val);
pre = cur;
cur = null;
}else{
stack.add(cur);
cur = cur.right;
}
}
return ret;
}
}
二叉树遍历是很基础的东西，大家一定要先理解清楚这部分内容后，再往下深入的学习。
递归与深度优先搜索(DFS)
很多新手会疑惑，左看右看深度优先搜索不就是递归了，干嘛还要起个装X的名字呢，然后DFS里面还有什么回溯、剪枝之类的，这些到底有什么区别？
在这里大家要区分下：数据结构、算法结构 和 算法思想。
比如，我们在上一章讲到了队列，然后通过队列实现了树的广度优先搜索。队列和广度优先搜索(BFS)，以及今天说到的递归与深度优先搜索(DFS)，有什么区别呢？
举个例子，我们国庆想从西安去北京旅游，这是我们的想法，然后怎么去？我们可以做高铁、飞机、自驾甚至骑行，这是我们实现旅游这个想法的方式和工具。
上述的例子用在算法中也是一样的，我们使用BFS的算法思想，通过队列的数据结构完成树的搜索。同样我们可以使用DFS的算法思想，通过递归这种算法结构实现了树的搜索。
但递归这种算法结构，其实隐含了(内存)栈的数据结构，这也就是我们在前中后序遍历中可以通过栈来实现迭代查询的操作基础。这几个名词一定要区分开，不要混淆了。
下面，我们来看一道使用DFS算法思想对二叉树进行剪枝的题目。
剑指OfferII047.二叉树剪枝
https://leetcode-cn.com/problems/pOCWxh/solution/jian-zhi-offerii047er-cha-shu-jian-zhi-p-6u4g/
难度：中等
题目
给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
节点 node 的子树为 node 本身，以及所有 node 的后代。
提示:
- 二叉树的节点个数的范围是 [1,200]
- 二叉树节点的值只会是 0 或 1
示例
示例 1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释: 只有红色节点满足条件“所有不包含 1 的子树”。下图为返回的答案。
1 1
\ \
0 --> 0
/ \ \
0 1 1
示例 2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
解释:
1 1
/ \ \
/ \ \
0 1 --> 1
/ \ / \ \
0 0 0 1 1
示例 3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
解释:
1 1
/ \ / \
/ \ / \
1 1 --> 1 1
/ \ / \ / \ \
1 1 0 1 1 1 1
/
0
分析
虽然这道题看似是让我们去剪枝，但其实仔细考虑下条件，我们从叶子节点网上逆推：
- 左子树为空
- 右子树为空
- node.val == 0
当满足以上三个条件时，将该叶子节点删除(node = null)，即可。
通过DFS后序遍历每个子节点，递归返回，就是最终的答案了。
解题：
Python:
class Solution:
def pruneTree(self, root):
if not root:
return root
root.left = self.pruneTree(root.left)
root.right = self.pruneTree(root.right)
if root.val == 0 and not root.left and not root.right:
return None
return root
Java:
class Solution {
public TreeNode pruneTree(TreeNode root) {
if( root == null) {
return root;
}
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.val == 0 && root.left == null && root.right == null){
root = null;
}
return root;
}
}
这道题是不是还比较简单....下来，我们来看一道有趣的题目。
大多数时候，我们所熟悉的树都是通过链式存储的非线性结构，但其实树还可以通过列表存储的线性结构来实现。通过下面这道题，你将了解为什么力扣上的树题目，都是由看似列表的字符串来实现的！
剑指OfferII048.序列化与反序列化二叉树
https://leetcode-cn.com/problems/h54YBf/solution/jian-zhi-offerii048xu-lie-hua-yu-fan-xu-i5xul/
难度：中等
题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：
- 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。
- 你并非必须采取这种方式，也可以采用其他的方法解决这个问题。
- 树中结点数在范围 [0, 10 ^ 4] 内
- -1000 <= Node.val <= 1000
示例
示例 1：
1
/ \
/ \
2 3
/ \
4 5
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
分析
大多数时候，我们所熟悉的树都是通过链式存储的非线性结构，但其实树还可以通过列表存储的线性结构来实现。
而这道题，在列表存储的基础上，让我们将列表转化为字符串，只是多了一道工序而已。
如果大家之前有了解过树的线性存储，相信这道题可以信手拈来。
BFS解题分析
- 这道题使用BFS的解题更为简单写，默认BFS时，需要判断当前节点是否有左、右子树
- 而此时，我们无需判断左右子树，当node为None时添加一个None到队列中即可。
DFS解题分析
- 在使用DFS时，势必将根节点放在第一个位置，可以方便我们反序列化，所以应该使用前序遍历。
- 遍历的时候同样注意，如果遇到空节点，需要将为空的节点也记录下来
- 即当一个子节点的左右节点都是None时，表示它其实是一个叶子节点。
- 反序列化时，同样通过前序遍历来实现，但注意默认的字符串转化为列表后，我们应该将从左到右遍历才满足条件
- Python我们可以反转列表或者使用deque的双端队列
- Java我们可以链表来实现
具体BFS、DFS解题如下：
BFS解题
Python:
from collections import deque
class Codec:
def serialize(self, root):
if not root:
return ""
dq = deque([root])
res = []
while dq:
node = dq.popleft()
if node:
res.append(str(node.val))
dq.append(node.left)
dq.append(node.right)
else:
res.append('None')
return ','.join(res)
def deserialize(self, data):
if not data:
return []
dataList = data.split(',')
root = TreeNode(int(dataList[0]))
dq = deque([root])
i = 1
while dq:
node = dq.popleft()
if dataList[i] != 'None':
node.left = TreeNode(int(dataList[i]))
dq.append(node.left)
i += 1
if dataList[i] != 'None':
node.right = TreeNode(int(dataList[i]))
dq.append(node.right)
i += 1
return root
Java:
public class Codec {
public String serialize(TreeNode root) {
if(root == null){
return "";
}
StringBuilder res = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node != null){
res.append("" + node.val);
queue.offer(node.left);
queue.offer(node.right);
}else{
res.append("null");
}
res.append(",");
}
return res.toString();
}
public TreeNode deserialize(String data) {
if(data == ""){
return null;
}
String[] dataList = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(dataList[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(!"null".equals(dataList[i])){
node.left = new TreeNode(Integer.parseInt(dataList[i]));
queue.offer(node.left);
}
i++;
if(!"null".equals(dataList[i])){
node.right = new TreeNode(Integer.parseInt(dataList[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
}
DFS解题
Python:
from collections import deque
class Codec:
def serialize(self, root):
if not root:
return 'None'
root.left = self.serialize(root.left)
root.right = self.serialize(root.right)
return f"{root.val},{root.left},{root.right}"
def deserialize(self, data):
dq = deque(data.split(','))
def dfs(li):
val = li.popleft()
if val == "None":
return None
root = TreeNode(int(val))
root.left = dfs(li)
root.right = dfs(li)
return root
return dfs(dq)
Java:
public class Codec {
public String serialize(TreeNode root) {
if(root == null){
return "null";
}
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
return dfs(queue);
}
private TreeNode dfs(Queue<String> queue) {
String val = queue.poll();
if("null".equals(val)){
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(val));
root.left = dfs(queue);
root.right = dfs(queue);
return root;
}
}
今天的树知识学习就到这里，这几道题可是很有意思的，大家一定要动手操作下哦！
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
