昨日回顧
昨天我們學(xué)習(xí)了樹的一些基礎(chǔ)名詞與分類昭卓，很多人想問黍特，為什么很多公司的手撕算法環(huán)節(jié)都會選擇樹這個(gè)數(shù)據(jù)類型來考察面試者呢？
因?yàn)闃渲邪闹R太多了薪丁。我們在昨天介紹的樹的前中后續(xù)遍歷中遇西，涉及到遞歸和迭代兩種方式馅精，單單這些就考察了我們對遞歸、棧粱檀、鏈表知識洲敢。更別說之前介紹過樹的逐層遍歷（廣度優(yōu)先搜索），以及之后要介紹的深度優(yōu)先搜索茄蚯。
說了這么多压彭，只是為了再次強(qiáng)調(diào)樹這個(gè)知識點(diǎn)的重要性。那么就要提問了渗常，昨天留的94和145題樹的中序和后續(xù)遍歷壮不，大家是否用兩種方法完成了呢？我猜基本都沒有皱碘。前序和中序在迭代的寫法中幾乎沒有差異忆畅，然而后續(xù)遍歷卻略顯復(fù)雜， 開篇先簡單帶著大家回顧下樹的后續(xù)遍歷知識吧尸执。
145.二叉樹的后序遍歷
難度：簡單
題目：
給定一個(gè)二叉樹，返回它的 后序 遍歷缓醋。
進(jìn)階: 遞歸算法很簡單如失，你可以通過迭代算法完成嗎？
示例：
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [3,2,1]
分析
對于遞歸的代碼前中后序遍歷送粱，只需要修改val添加的位置即可褪贵。
但對于迭代的操作，則后續(xù)遍歷稍顯麻煩抗俄。
因?yàn)樽?-> 右 -> 中 的訪問過程中如果沒有控制好右側(cè)節(jié)點(diǎn)的鏈表指向脆丁，可能會造成死循環(huán)的問題。
解決問題的關(guān)鍵动雹，當(dāng)遍歷到右節(jié)點(diǎn)為空的狀態(tài)時(shí)槽卫，需要記錄他的pre節(jié)點(diǎn)，避免造成棧與鏈表的循環(huán)訪問即可胰蝠。
遞歸解題：
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;
}
}
二叉樹遍歷是很基礎(chǔ)的東西歼培，大家一定要先理解清楚這部分內(nèi)容后，再往下深入的學(xué)習(xí)茸塞。
遞歸與深度優(yōu)先搜索(DFS)
很多新手會疑惑躲庄，左看右看深度優(yōu)先搜索不就是遞歸了，干嘛還要起個(gè)裝X的名字呢钾虐，然后DFS里面還有什么回溯噪窘、剪枝之類的，這些到底有什么區(qū)別效扫？
在這里大家要區(qū)分下：數(shù)據(jù)結(jié)構(gòu)倔监、算法結(jié)構(gòu) 和 算法思想直砂。
比如，我們在上一章講到了隊(duì)列丐枉，然后通過隊(duì)列實(shí)現(xiàn)了樹的廣度優(yōu)先搜索哆键。隊(duì)列和廣度優(yōu)先搜索(BFS)，以及今天說到的遞歸與深度優(yōu)先搜索(DFS)瘦锹，有什么區(qū)別呢籍嘹？
舉個(gè)例子，我們國慶想從西安去北京旅游弯院，這是我們的想法辱士，然后怎么去？我們可以做高鐵听绳、飛機(jī)颂碘、自駕甚至騎行，這是我們實(shí)現(xiàn)旅游這個(gè)想法的方式和工具椅挣。
上述的例子用在算法中也是一樣的头岔，我們使用BFS的算法思想，通過隊(duì)列的數(shù)據(jù)結(jié)構(gòu)完成樹的搜索鼠证。同樣我們可以使用DFS的算法思想峡竣，通過遞歸這種算法結(jié)構(gòu)實(shí)現(xiàn)了樹的搜索。
但遞歸這種算法結(jié)構(gòu)量九，其實(shí)隱含了(內(nèi)存)棧的數(shù)據(jù)結(jié)構(gòu)适掰，這也就是我們在前中后序遍歷中可以通過棧來實(shí)現(xiàn)迭代查詢的操作基礎(chǔ)。這幾個(gè)名詞一定要區(qū)分開荠列，不要混淆了类浪。
下面，我們來看一道使用DFS算法思想對二叉樹進(jìn)行剪枝的題目肌似。
劍指OfferII047.二叉樹剪枝
https://leetcode-cn.com/problems/pOCWxh/solution/jian-zhi-offerii047er-cha-shu-jian-zhi-p-6u4g/
難度：中等
題目
給定一個(gè)二叉樹 根節(jié)點(diǎn) root 费就，樹的每個(gè)節(jié)點(diǎn)的值要么是 0，要么是 1川队。請剪除該二叉樹中所有節(jié)點(diǎn)的值為 0 的子樹受楼。
節(jié)點(diǎn) node 的子樹為 node 本身，以及所有 node 的后代呼寸。
提示:
- 二叉樹的節(jié)點(diǎn)個(gè)數(shù)的范圍是 [1,200]
- 二叉樹節(jié)點(diǎn)的值只會是 0 或 1
示例
示例 1:
輸入: [1,null,0,0,1]
輸出: [1,null,0,null,1]
解釋: 只有紅色節(jié)點(diǎn)滿足條件“所有不包含 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
分析
雖然這道題看似是讓我們?nèi)ゼ糁Χ匝鋵?shí)仔細(xì)考慮下條件河狐，我們從葉子節(jié)點(diǎn)網(wǎng)上逆推：
- 左子樹為空
- 右子樹為空
- node.val == 0
當(dāng)滿足以上三個(gè)條件時(shí)，將該葉子節(jié)點(diǎn)刪除(node = null)，即可馋艺。
通過DFS后序遍歷每個(gè)子節(jié)點(diǎn)栅干，遞歸返回，就是最終的答案了捐祠。
解題：
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;
}
}
這道題是不是還比較簡單....下來碱鳞，我們來看一道有趣的題目。
大多數(shù)時(shí)候踱蛀，我們所熟悉的樹都是通過鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)窿给，但其實(shí)樹還可以通過列表存儲的線性結(jié)構(gòu)來實(shí)現(xiàn)。通過下面這道題率拒，你將了解為什么力扣上的樹題目崩泡，都是由看似列表的字符串來實(shí)現(xiàn)的！
劍指OfferII048.序列化與反序列化二叉樹
https://leetcode-cn.com/problems/h54YBf/solution/jian-zhi-offerii048xu-lie-hua-yu-fan-xu-i5xul/
難度：中等
題目
序列化是將一個(gè)數(shù)據(jù)結(jié)構(gòu)或者對象轉(zhuǎn)換為連續(xù)的比特位的操作猬膨，進(jìn)而可以將轉(zhuǎn)換后的數(shù)據(jù)存儲在一個(gè)文件或者內(nèi)存中角撞，
同時(shí)也可以通過網(wǎng)絡(luò)傳輸?shù)搅硪粋€(gè)計(jì)算機(jī)環(huán)境，采取相反方式重構(gòu)得到原數(shù)據(jù)勃痴。
請?jiān)O(shè)計(jì)一個(gè)算法來實(shí)現(xiàn)二叉樹的序列化與反序列化谒所。這里不限定你的序列 / 反序列化算法執(zhí)行邏輯，
只需要保證一個(gè)二叉樹可以被序列化為一個(gè)字符串并且將這個(gè)字符串反序列化為原始的樹結(jié)構(gòu)沛申。
提示：
- 輸入輸出格式與 LeetCode 目前使用的方式一致百炬，詳情請參閱 LeetCode 序列化二叉樹的格式。
- 你并非必須采取這種方式污它，也可以采用其他的方法解決這個(gè)問題。
- 樹中結(jié)點(diǎn)數(shù)在范圍 [0, 10 ^ 4] 內(nèi)
- -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]
分析
大多數(shù)時(shí)候庶弃，我們所熟悉的樹都是通過鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)衫贬，但其實(shí)樹還可以通過列表存儲的線性結(jié)構(gòu)來實(shí)現(xiàn)。
而這道題歇攻，在列表存儲的基礎(chǔ)上固惯，讓我們將列表轉(zhuǎn)化為字符串，只是多了一道工序而已缴守。
如果大家之前有了解過樹的線性存儲葬毫，相信這道題可以信手拈來。
BFS解題分析
- 這道題使用BFS的解題更為簡單寫屡穗，默認(rèn)BFS時(shí)贴捡，需要判斷當(dāng)前節(jié)點(diǎn)是否有左、右子樹
- 而此時(shí)村砂，我們無需判斷左右子樹烂斋，當(dāng)node為None時(shí)添加一個(gè)None到隊(duì)列中即可。
DFS解題分析
- 在使用DFS時(shí)，勢必將根節(jié)點(diǎn)放在第一個(gè)位置汛骂，可以方便我們反序列化罕模，所以應(yīng)該使用前序遍歷。
- 遍歷的時(shí)候同樣注意帘瞭，如果遇到空節(jié)點(diǎn)淑掌，需要將為空的節(jié)點(diǎn)也記錄下來
- 即當(dāng)一個(gè)子節(jié)點(diǎn)的左右節(jié)點(diǎn)都是None時(shí)，表示它其實(shí)是一個(gè)葉子節(jié)點(diǎn)蝶念。
- 反序列化時(shí)抛腕，同樣通過前序遍歷來實(shí)現(xiàn)，但注意默認(rèn)的字符串轉(zhuǎn)化為列表后祸轮，我們應(yīng)該將從左到右遍歷才滿足條件
- Python我們可以反轉(zhuǎn)列表或者使用deque的雙端隊(duì)列
- Java我們可以鏈表來實(shí)現(xiàn)
具體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;
}
}
今天的樹知識學(xué)習(xí)就到這里，這幾道題可是很有意思的适袜，大家一定要?jiǎng)邮植僮飨屡叮?/p>
歡迎關(guān)注我的公眾號: 清風(fēng)Python柄错，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)，了解更多python小知識苦酱。
我的個(gè)人博客：https://qingfengpython.cn
