我們開始介紹“二叉樹和遞歸”听盖。遞歸，是使用計算機(jī)解決問題的一種重要的思考方式幢痘。而二叉樹由于其天然的遞歸結(jié)構(gòu)唬格，使得基于二叉樹的算法家破，均擁有著遞歸性質(zhì)颜说。使用二叉樹，是研究學(xué)習(xí)遞歸算法的最佳入門方式汰聋。在這一章里门粪，我們就來看一看二叉樹中的遞歸算法。
在前面知識的學(xué)習(xí)中烹困，我們看到了在基礎(chǔ)算法以及系統(tǒng)設(shè)計中都用到了遞歸玄妈。深度優(yōu)先遍歷中也用到了遞歸。從這一部分開始髓梅，我們從另一個視角看遞歸拟蜻。
從二叉樹的角度看遞歸
二叉樹天然具有遞歸的性質(zhì)。二叉樹的定義就是用二叉樹定義二叉樹枯饿。對于二叉樹的定義來說酝锅，應(yīng)該補(bǔ)充一點(diǎn)：空是一棵二叉樹。
下面奢方，我們來觀察一個二叉樹的前序遍歷的遞歸方法搔扁。
Java 代碼：
public void preorder(TreeNode node){
if(node != null){
System.out.print(node.val);
preorder(node.left);
preorder(node.right);
}
}
注意：這里 System.out.print(node.val); 這一行代碼表示“處理這個結(jié)點(diǎn)的邏輯”。
在這里蟋字，我們先強(qiáng)調(diào)編寫遞歸函數(shù)的第 1 個注意事項：首先明確這個函數(shù)要表達(dá)的任務(wù)（邏輯）稿蹲，明確參數(shù)的定義和返回值的意義。
接下來鹊奖，我們將上面的代碼改造一下苛聘。
Java 代碼：
public void preorder(TreeNode node){
// 先寫遞歸終止條件
if(node == null){
return;
}
// 再寫遞歸過程
System.out.print(node.val);
preorder(node.left);
preorder(node.right);
}
其實(shí)這樣的寫法更像遞歸結(jié)構(gòu)，因?yàn)閷τ谖覀兌x的每一個遞歸函數(shù)來說忠聚，應(yīng)該包含下面兩個部分：1焰盗、遞歸終止條件；2咒林、設(shè)立遞歸過程熬拒，定義清楚函數(shù)的語義。
這就是我們編寫一個遞歸函數(shù)應(yīng)該注意的第 2 件事情垫竞。
接下來澎粟，我們再看一個方法：在一個二叉樹中查看是否存在一個鍵值蛀序。寫這個遞歸方法的步驟：想想（1）遞歸終止條件是什么？（2）遞歸過程是什么活烙？參數(shù) Node node 是什么意思徐裸？我們這里定義的參數(shù) Node 對象，是在以 node 為根結(jié)點(diǎn)的二叉樹中尋找指定的 key啸盏。于是重贺，我們的邏輯是：如果 node 本身不是我們要找的結(jié)點(diǎn)的話，我們繼續(xù)在 node 的左孩子和右孩子中繼續(xù)查找回懦。
Java 代碼：
public boolean contain(Node node, int key) {
// 首先我們要處理遞歸到底的情況
if (node == null) {
return false;
}
if (key == node.key) {
return true;
}
if (contain(node.left, key) || contain(node.right, key) {
return true;
}
return false;
}
那么气笙，我們可以再想想如何釋放以 Node 為根結(jié)點(diǎn)的二叉樹？
例題
例1：LeetCode 第 104 題：求一棵二叉樹的最大深度怯晕。
傳送門：英文網(wǎng)址：104. Maximum Depth of Binary Tree 潜圃，中文網(wǎng)址：104. 二叉樹的最大深度 。
給定一個二叉樹舟茶，找出其最大深度谭期。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)吧凉。
示例：
給定二叉樹[3,9,20,null,null,15,7]隧出，3 / \ 9 20 / \ 15 7返回它的最大深度 3 。
關(guān)鍵：要能看出這道題本質(zhì)上是二叉樹的后序遍歷阀捅。
Python 代碼：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
# 先計算左右子樹胀瞪，然后再計算自己，這是后序遍歷
l_sub_tree_depth = self.maxDepth(root.left)
r_sub_tree_depth = self.maxDepth(root.right)
return max(l_sub_tree_depth, r_sub_tree_depth) + 1
Python 代碼：把上面的遞歸改成循環(huán)
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
depth = 0
stack = [(1, root)]
while stack:
cur_depth, node = stack.pop()
depth = max(depth, cur_depth)
if node.left:
stack.append((cur_depth + 1, node.left))
if node.right:
stack.append((cur_depth + 1, node.right))
return depth
說明：這個寫法看一看就好也搓，感覺沒啥意思赏廓。
感覺遞歸調(diào)用就像什么都沒有做一樣。通過這個例子傍妒，我們來理解一下（1）（2）這兩個步驟的具體應(yīng)用幔摸。這讓我想起了八皇后問題。
還可以使用 DFS 和 BFS 完成這個問題颤练。首先 BFS 我覺得思路更直接一些既忆，代碼也是有套路的。
Python 代碼：
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
depth = 0
queue = [root]
while queue:
size = len(queue)
depth += 1
for _ in range(size):
first = queue.pop(0)
if first.left:
queue.append(first.left)
if first.right:
queue.append(first.right)
return depth
Python 代碼：使用 DFS
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 求一棵二叉樹的最大深度嗦玖。
# 要能看出這道題本質(zhì)上是二叉樹的后序遍歷患雇。
class Solution(object):
def __init__(self):
self.max_depth = 0
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
self.__dfs(root, 0)
return self.max_depth
def __dfs(self, node, depth):
if node is None:
return
depth += 1
if node.left is None and node.right is None:
# 到葉子結(jié)點(diǎn)了，可以結(jié)算了
self.max_depth = max(self.max_depth, depth)
return
if node.left:
self.__dfs(node.left, depth)
if node.right:
self.__dfs(node.right, depth)
- 復(fù)習(xí)和二叉樹相關(guān)的所有操作宇挫。
練習(xí)
練習(xí)1：LeetCode 第 111 題：求一棵二叉樹的最小深度苛吱。
傳送門：英文網(wǎng)址：111. Minimum Depth of Binary Tree ，中文網(wǎng)址：111. 二叉樹的最小深度 器瘪。
給定一個二叉樹翠储，找出其最小深度绘雁。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)援所。
示例:
給定二叉樹
[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回它的最小深度 2.
分析：即求一棵二叉樹從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最短路徑的長度庐舟。
這個問題里面有小的陷阱。
我們在思考遞歸終止條件的時候住拭，有的時候可能會存在陷阱挪略。
這道題，我第一次做是想當(dāng)然滔岳，順著第 104 題把最大改成最小杠娱，但是要注意到上圖 4 那個結(jié)點(diǎn)，4 的左孩子為空澈蟆，返回 0 卓研，右孩子為 9趴俘，返回2奏赘，按照我們的邏輯就返回 0 ，顯然是錯誤的磨淌，所以要針對左右孩子有一個為空的時候疲憋，做出分類判斷梁只。
Python 代碼：
# Definition for a binary tree node.
# 111. 二叉樹的最小深度
# 給定一個二叉樹，找出其最小深度搪锣。
#
# 最小深度是從根結(jié)點(diǎn)到最近葉子結(jié)點(diǎn)的最短路徑上的結(jié)點(diǎn)數(shù)量。
#
# 說明: 葉子結(jié)點(diǎn)是指沒有子結(jié)點(diǎn)的結(jié)點(diǎn)构舟。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
if root.left is None:
return 1 + self.minDepth(root.right)
if root.right is None:
return 1 + self.minDepth(root.left)
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
Python 代碼：使用 BFS：==使用層序遍歷灰追，我感覺更直接一些，因?yàn)橹灰獟叩饺~子結(jié)點(diǎn)狗超，就可以返回了==
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
depth = 0
queue = [root]
while queue:
depth += 1
size = len(queue)
for _ in range(size):
first = queue.pop(0)
if first.left is None and first.right is None:
return depth
if first.left:
queue.append(first.left)
if first.right:
queue.append(first.right)
Python 代碼：使用 DFS
# Definition for a binary tree node.
# 111. 二叉樹的最小深度
# 給定一個二叉樹弹澎，找出其最小深度。
#
# 最小深度是從根結(jié)點(diǎn)到最近葉子結(jié)點(diǎn)的最短路徑上的結(jié)點(diǎn)數(shù)量努咐。
#
# 說明: 葉子結(jié)點(diǎn)是指沒有子結(jié)點(diǎn)的結(jié)點(diǎn)苦蒿。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def __init__(self):
self.min_depth = float("inf")
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
self.__dfs(root, 0)
return self.min_depth
def __dfs(self, node, depth):
if node is None:
return
depth += 1
if node.left is None and node.right is None:
self.min_depth = min(self.min_depth, depth)
return
if node.left:
self.__dfs(node.left, depth)
if node.right:
self.__dfs(node.right, depth)
（本節(jié)完）
