我們開(kāi)始介紹“二叉樹(shù)和遞歸”。遞歸，是使用計(jì)算機(jī)解決問(wèn)題的一種重要的思考方式。而二叉樹(shù)由于其天然的遞歸結(jié)構(gòu)，使得基于二叉樹(shù)的算法，均擁有著遞歸性質(zhì)。使用二叉樹(shù)，是研究學(xué)習(xí)遞歸算法的最佳入門(mén)方式。在這一章里，我們就來(lái)看一看二叉樹(shù)中的遞歸算法。
在前面知識(shí)的學(xué)習(xí)中，我們看到了在基礎(chǔ)算法以及系統(tǒng)設(shè)計(jì)中都用到了遞歸。深度優(yōu)先遍歷中也用到了遞歸。從這一部分開(kāi)始，我們從另一個(gè)視角看遞歸。
從二叉樹(shù)的角度看遞歸
二叉樹(shù)天然具有遞歸的性質(zhì)。二叉樹(shù)的定義就是用二叉樹(shù)定義二叉樹(shù)。對(duì)于二叉樹(shù)的定義來(lái)說(shuō)，應(yīng)該補(bǔ)充一點(diǎn)：空是一棵二叉樹(shù)。
下面，我們來(lái)觀察一個(gè)二叉樹(shù)的前序遍歷的遞歸方法。
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); 這一行代碼表示“處理這個(gè)結(jié)點(diǎn)的邏輯”。
在這里，我們先強(qiáng)調(diào)編寫(xiě)遞歸函數(shù)的第 1 個(gè)注意事項(xiàng)：首先明確這個(gè)函數(shù)要表達(dá)的任務(wù)（邏輯），明確參數(shù)的定義和返回值的意義。
接下來(lái)，我們將上面的代碼改造一下。
Java 代碼：
public void preorder(TreeNode node){
// 先寫(xiě)遞歸終止條件
if(node == null){
return;
}
// 再寫(xiě)遞歸過(guò)程
System.out.print(node.val);
preorder(node.left);
preorder(node.right);
}
其實(shí)這樣的寫(xiě)法更像遞歸結(jié)構(gòu)，因?yàn)閷?duì)于我們定義的每一個(gè)遞歸函數(shù)來(lái)說(shuō)，應(yīng)該包含下面兩個(gè)部分：1、遞歸終止條件；2、設(shè)立遞歸過(guò)程，定義清楚函數(shù)的語(yǔ)義。
這就是我們編寫(xiě)一個(gè)遞歸函數(shù)應(yīng)該注意的第 2 件事情。
接下來(lái)，我們?cè)倏匆粋€(gè)方法：在一個(gè)二叉樹(shù)中查看是否存在一個(gè)鍵值。寫(xiě)這個(gè)遞歸方法的步驟：想想（1）遞歸終止條件是什么？（2）遞歸過(guò)程是什么？參數(shù) Node node 是什么意思？我們這里定義的參數(shù) Node 對(duì)象，是在以 node 為根結(jié)點(diǎn)的二叉樹(shù)中尋找指定的 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)的二叉樹(shù)？
例題
例1：LeetCode 第 104 題：求一棵二叉樹(shù)的最大深度。
傳送門(mén)：英文網(wǎng)址：104. Maximum Depth of Binary Tree ，中文網(wǎng)址：104. 二叉樹(shù)的最大深度 。
給定一個(gè)二叉樹(shù)，找出其最大深度。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：
給定二叉樹(shù)[3,9,20,null,null,15,7]，3 / \ 9 20 / \ 15 7返回它的最大深度 3 。
關(guān)鍵：要能看出這道題本質(zhì)上是二叉樹(shù)的后序遍歷。
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
# 先計(jì)算左右子樹(shù)，然后再計(jì)算自己，這是后序遍歷
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
說(shuō)明：這個(gè)寫(xiě)法看一看就好，感覺(jué)沒(méi)啥意思。
感覺(jué)遞歸調(diào)用就像什么都沒(méi)有做一樣。通過(guò)這個(gè)例子，我們來(lái)理解一下（1）（2）這兩個(gè)步驟的具體應(yīng)用。這讓我想起了八皇后問(wèn)題。
還可以使用 DFS 和 BFS 完成這個(gè)問(wèn)題。首先 BFS 我覺(jué)得思路更直接一些，代碼也是有套路的。
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
# 求一棵二叉樹(shù)的最大深度。
# 要能看出這道題本質(zhì)上是二叉樹(shù)的后序遍歷。
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í)和二叉樹(shù)相關(guān)的所有操作。
練習(xí)
練習(xí)1：LeetCode 第 111 題：求一棵二叉樹(shù)的最小深度。
傳送門(mén)：英文網(wǎng)址：111. Minimum Depth of Binary Tree ，中文網(wǎng)址：111. 二叉樹(shù)的最小深度 。
給定一個(gè)二叉樹(shù)，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定二叉樹(shù)
[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回它的最小深度 2.
分析：即求一棵二叉樹(shù)從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最短路徑的長(zhǎng)度。
這個(gè)問(wèn)題里面有小的陷阱。
我們?cè)谒伎歼f歸終止條件的時(shí)候，有的時(shí)候可能會(huì)存在陷阱。
這道題，我第一次做是想當(dāng)然，順著第 104 題把最大改成最小，但是要注意到上圖 4 那個(gè)結(jié)點(diǎn)，4 的左孩子為空，返回 0 ，右孩子為 9，返回2，按照我們的邏輯就返回 0 ，顯然是錯(cuò)誤的，所以要針對(duì)左右孩子有一個(gè)為空的時(shí)候，做出分類(lèi)判斷。
Python 代碼：
# Definition for a binary tree node.
# 111. 二叉樹(shù)的最小深度
# 給定一個(gè)二叉樹(shù)，找出其最小深度。
#
# 最小深度是從根結(jié)點(diǎn)到最近葉子結(jié)點(diǎn)的最短路徑上的結(jié)點(diǎn)數(shù)量。
#
# 說(shuō)明: 葉子結(jié)點(diǎn)是指沒(méi)有子結(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：==使用層序遍歷，我感覺(jué)更直接一些，因?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. 二叉樹(shù)的最小深度
# 給定一個(gè)二叉樹(shù)，找出其最小深度。
#
# 最小深度是從根結(jié)點(diǎn)到最近葉子結(jié)點(diǎn)的最短路徑上的結(jié)點(diǎn)數(shù)量。
#
# 說(shuō)明: 葉子結(jié)點(diǎn)是指沒(méi)有子結(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é)完）
