1 樹的基本知識

1.1 概念

樹，結合了鏈表與圖。

①單鏈表：一個數據域+一個指針域；樹：一個數據域＋多個指針域。

②樹是無環連通圖。

1.2 定義

樹是N個節點的有限集合，N=0為空樹，N>0時應當滿足：

①有且僅有一個特定的稱為根的節點；

②N>1時，其余節點可分為m個互不相交的有限集合，其中每個有限集合自身又是一棵樹（遞歸定義）。

1.3 重要的樹：二叉樹（屬于有序樹）

滿二叉樹、完全二叉樹、二叉搜索樹（BST）、平衡二叉樹（典型應用是平衡二叉搜索樹）

2 樹的存儲結構

2.1順序存儲

[類似于鄰接表的存儲方法] 父子節點表示法、父節點表示法、子節點表示法

2.2鏈式存儲

類似于鏈表：

#普通的樹中的節點 class TreeNode:def __init__(self,val=0,children=None):self.val=valself.children=children if children is not None else []#二叉樹中的節點 class TreeNode(object):def __init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right

3 樹的基本操作

? 關于樹的增刪改查，其核心是“查查查查”，即查找、搜索、遍歷是樹的核心操作。而對于樹的查找、搜索、遍歷，主要有兩種思路，分別是深度優先搜索（DFS）和廣度優先搜索（BFS）。

3.1 深度優先搜索（DFS）

? 深度優先搜索是一種遞歸式的方法，因為它一定要按一定的規則規律向深處探索，而這種規律便分為三種，分別是前序、中序和后序。以前序為例，其順序為“根、左、右”，那么對于每一個子樹，都要按照這個順序，先搜索根節點，然后搜索其左子樹，再搜索其右子樹，形成遞歸調用棧，觸底后回溯。而中序和后序，只是幾個遞歸句子和操作句子的順序不太一樣罷了。

這里我們假設操作句子為print，那么：

#1 前序 def dfs(TreeNode root):if not root:return Noneprint(root.val) #操作dfs(root.left)dfs(root.right)#2 中序 def dfs(TreeNode root):if not root:return Nonedfs(root.left)print(root.val)#操作dfs(root.right)#3 后序 def dfs(TreeNode root):if not root:return Nonedfs(root.left)dfs(root.right)print(root.val)#操作

? 可以看到，深度優先搜索的關鍵點，一方面在于“深度優先”，也就是它先伸到底的這個特性；另一方面就是它帶來的附加特性，即它必須要依照一定的規則、順序來搜索，而這個規則要適用于任何子樹，又因為樹本身的定義就是遞歸的，所以自然也要遞歸地進行步驟，而一旦遞歸了，自然也就實現了“深度”，因為遞歸的終止條件是觸底，觸底后才會回溯，才能得到之前的結果，才能完成這一步，才能繼續進行下去。

3.2 廣度優先搜索（BFS）

? 廣度優先搜索是一種普通的迭代遍歷方法，其規則是既定的，即從根節點開始，按層次從上到下，同層次內從左到右 “ 訪問（/操作）” 每一個節點，每個節點只會經歷一次（與DFS相對，DFS雖然也只操作一次，但會經歷多次）。

? 廣度優先搜索的關鍵點是借助“隊列”數據結構，對于隊列的使用只需創建一個空列表，入隊用append在隊尾加入，出隊用pop(0)在隊頭彈出。

#1 常規的BFS實現代碼 def bfs(self,root):q=[]q.append(root)while q and q[0]: #這句and q[0]太重要了！！！因為有可能[none]，也就是根節點為none#這里q[0]是為了避免root==None的情況，但它只會在初始條件時存在，因此也可改寫成3cur=q.pop(0)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)return xxx#2 分層次的BFS實現代碼 def bfs(self,root):q=[]q.append(root)#這里q[0]是為了避免root==None的情況，但它只會在初始條件時存在，因此也可改寫成3while q and q[0]: #控制層次級別操作l=len(q)for i in range(l): #控制同一層內節點級別操作cur=q.pop(0)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)return xxx#3 改變初始空值處理方法 def bfs(self,root):if not root:returnq=[]q.append(root)while q: #控制層次級別操作l=len(q)for i in range(l): #控制同一層內節點級別操作cur=q.pop(0)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)return xxx

• 分層次的合理性：并沒有增加時間復雜度，雖然看似變成了雙重循環，但是實際上內部循環占比和為1，相當于那種加權感，仍然實質上是一層循環。

• 分層次的好處：將層次級操作與層內節點級操作分離開來，從最表象的優點來看，至少可以知道每一層節點的數目，以及節點所處的層數了。

4 重點例題

4.1 二叉樹的最大深度

①BFS

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""q=[]q.append(root)cnt=0while q and q[0]:l=len(q)cnt+=1for i in range(l):cur=q.pop(0)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)return cnt

②DFS（后序遍歷）

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0#遞歸結束條件if not root.left and not root.right:return 1#遞歸大致邏輯return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

③DFS（先序遍歷）

class Solution(object):def dfs(self,root,temp,ans):#遞歸終止條件if not root:self.ans=max(self.ans,temp) #每次觸底，都要看看temp能否更新最大深度#遞歸主體temp+=1 #每調用一次自身，都記錄一次（相當于先序遍歷中對于自己的那一句操作）self.dfs(root.left,temp,self.ans)self.dfs(root.right,temp,self.ans)def maxDepth(self, root):""":type root: TreeNode:rtype: int"""temp=0self.ans=0self.dfs(root,temp,self.ans)return self.ans

4.2 二叉樹的最小深度

? 這里我一開始犯了個錯誤，就是沒仔細想就直接莽撞地把求最大深度的地后序DFS套用了，但實際上它們是非常不一樣的。最大深度的終止（觸底）條件是它是葉節點，當然，最小深度的觸底條件相同，但是有的時候它只有右子樹沒有左子樹，這個時候不能莽撞地取了左子樹作為min（第一次提交就是這么錯的），也就是說，必須要么左右子樹都有，才min地遞歸下去，要么左右子樹都沒有，就等待觸底地遞歸下去，要是只有左子樹或者只有右子樹，則要單側遞歸下去（當然，如果它的子樹就恢復了，還是繼續可以雙min遞歸的。）

①DFS后序

#1 丑陋的敷衍版 class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0if root.left and root.right:return min(self.minDepth(root.left),self.minDepth(root.right))+1if root.left and not root.right:return self.minDepth(root.left)+1elif root.right and not root.left:return self.minDepth(root.right)+1elif not root.left and not root.right:return 1#2 整理清爽版 class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""#遞歸終止條件if not root:return 0#if root.left==root.right: 這句不可以，因為好像是true and true這樣是布爾型，但用==就是指相同的子樹了if (root.left and root.right) or (not root.left and not root.right):return min(self.minDepth(root.left),self.minDepth(root.right))+1if root.left:return self.minDepth(root.left)+1else:return self.minDepth(root.right)+1

②DFS（先序）

class Solution(object):def dfs(self, root, temp, ans):#1 遞歸終止條件if not root: #由于min的特殊性，可能會導致self.ans無法增長，因此選擇觸底后再判斷就可以解決這個問題if self.ans!=0:self.ans=min(self.ans,temp)else:self.ans=tempreturn #這里必須有個空return來終止遞歸temp+=1 #操作#對于左右的操作分情況討論，就可以做到符合最小深度性質，避免之前說的那種問題if (root.left and root.right) or (not root.left and not root.right):self.dfs(root.left,temp,self.ans)self.dfs(root.right,temp,self.ans)return #這里用上return，才能避免下面的需要套一個大elseif root.left:self.dfs(root.left,temp,self.ans)else:self.dfs(root.right,temp,self.ans)returndef minDepth(self, root):""":type root: TreeNode:rtype: int"""temp=0self.ans=0self.dfs(root,temp,self.ans)return self.ans

③BFS

class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""q=[]q.append(root)cnt=0while q and q[0]:l=len(q)cnt+=1for i in range(l):cur=q.pop(0)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)if not cur.left and not cur.right:return cnt#break不可以的，因為break只能跳出一層循環，無法跳出嵌套，但是如果在外面硬加一個break就會變成強行無條件跳出了，所以這里只能returnreturn cnt #這個是為了解決[]要返回0的問題

4.3將有序數組轉換為二叉搜索樹

方法：二分遞歸

構造思路：

? 首先，知道一個常識，即“二叉搜索樹的中序遍歷（左中右）是升序序列”，那么我們要從一個升序序列構造一棵二叉搜索樹，則是把它反過來的操作，這個升序數組遞歸地符合“左邊是左子樹，中間是根節點，右邊是右子樹”，但是我們要構造一棵樹，只能先構造根節點再構造其左子樹右子樹，因此要從中間開始遞歸地先構造根節點，再左右子樹。

? 其次，要求是高度平衡的二叉樹，所以左右子樹高度差不能超過1，使用二分法可以確保其平衡，即每次左右子樹都最多差1，這樣遞歸地進行下去，左右子樹最多還是差1（仔細模擬著想一下就可以）。

關于唯一性：

? 即使明確要求了它高度平衡，其仍然不唯一，因為在二分時如果有偶數，仍然有選左邊和選右邊的區別。因此即使是要求高度平衡，根據中序遍歷序列構造出的二叉樹也不是唯一的（不要求高度平衡的就更別說了）。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object):def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""if not nums:returnmid=len(nums)//2root=TreeNode(val=nums[mid])root.left=self.sortedArrayToBST(nums[:mid])root.right=self.sortedArrayToBST(nums[mid+1:])return root

4.4 從中序與后序遍歷序列構造二叉樹

①遞歸

? 前面說了，僅由一個遍歷序無法確定唯一的一個二叉樹，但知道兩個序的遍歷就能確定一個了。整體思路，因為是樹相關的題目，所以還是遞歸或者迭代，然后就是考慮中序和后序怎么充分發揮自身特性并結合起來了，其結合的思路大抵如下：

? 中序遍歷（左中右），特點是可以二分地遞歸構造出這棵樹（上一個題已經充分展現和理解了這一點）；而后序遍歷（左右中），其特點是對于每一顆子樹的部分，最后一位都是它的根節點（其實推廣一下，如果知道的是前序遍歷，也可以利用其第一位是根節點的特性）。分別理解了它們各自的特性之后，還有很關鍵的一點就是把它們銜接起來：①首先通過后序遍歷的末尾得到根節點，然后在中序找到這個節點并記錄下其位置，則是中序二分的分點；②因為后序想要找下一層的根節點需要跳幾格，但不知道怎么找，這時候就要借助到中序上一步二分開左右的長度了，通過這樣長度的跨越，就可以找到新的兩個分點，再從中序序列里進行二分，自此遞歸地進行下去。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object):def buildTree(self, inorder, postorder):""":type inorder: List[int]:type postorder: List[int]:rtype: TreeNode"""#遞歸終止條件if not inorder and not postorder:return#大體實現邏輯a=postorder[-1]p=inorder.index(a)leftin=inorder[:p]rightin=inorder[p+1:]ll=len(leftin)lr=len(rightin)next_left=postorder[ll-1]next_right=postorder[ll+lr-1]root=TreeNode(val=a)root.left=self.buildTree(leftin,postorder[:ll])root.right=self.buildTree(rightin,postorder[ll:ll+lr])return root

②迭代

……有點復雜…有時間再說吧

4.5 從前序與中序遍歷序列構造二叉樹

和上一題基本完全一樣。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""#遞歸終止條件if not preorder and not inorder:return#整體實現邏輯a=preorder[0]p=inorder.index(a)leftin=inorder[:p]rightin=inorder[p+1:]ll=len(leftin)root=TreeNode(val=a)root.left=self.buildTree(preorder[1:ll+1],inorder[:ll])root.right=self.buildTree(preorder[ll+1:],inorder[ll+1:])return root

總結

以上是生活随笔為你收集整理的datawhale组队学习笔记（3）树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。