1.學習目標

1.1 二叉樹

實現一個二叉查找樹，并且支持插入、刪除、查找操作
實現查找二叉查找樹中某個節點的后繼、前驅節點
實現二叉樹前、中、后序以及按層遍歷

1.2 堆

實現一個小頂堆、大頂堆、優先級隊列
實現堆排序
利用優先級隊列合并 K 個有序數組
求一組動態數據集合的最大 Top K

1.3 對應的 LeetCode 練習題

Invert Binary Tree（翻轉二叉樹）
英文版：Loading…
中文版：力扣

Maximum Depth of Binary Tree（二叉樹的最大深度）
英文版：Loading…
中文版：力扣

Validate Binary Search Tree（驗證二叉查找樹）
英文版：Loading…
中文版：力扣

Path Sum（路徑總和）
英文版：Loading…
中文版：力扣

2. 學習內容

2.1 二叉樹

定義：
左子樹不為空的時候，左子樹的節點值小于根結點
右子樹不為空的時候，右子樹的節點值大于根結點
左右子數據分別為二叉查找樹
二叉查找樹最左邊的節點即為最小值，要查找最小值，僅需遍歷左子樹的節點值到空為止
二叉查找樹的插入/查找/刪除操作都是通過遞歸方式實現的。刪除一個節點：
先找到這個節點S，假設節點左右孩子都不為空
在其右子樹找到后繼(最小)節點，將后繼節點的值給S
刪除該后繼節點

實現一個二叉查找樹，并且支持插入、刪除、查找操作
實現查找二叉查找樹中某個節點的后繼、前驅節點
實現二叉樹前、中、后序以及按層遍歷

class Node:def __init__(self, data):self.data = dataself.lchild = Noneself.rchild = Noneclass BST:def __init__(self, node_list):self.root = Node(node_list[0])for data in node_list[1:]:self.insert(data)def search(self, node, parent, data):  # 搜索if node is None:return False, node, parentif node.data == data:return True, node, parentif node.data > data:return self.search(node.lchild, node, data)else:return self.search(node.rchild, node, data)def insert(self, data):  # 插入flag, n, p = self.search(self.root, self.root, data)if not flag:new_node = Node(data)if data > p.data:p.rchild = new_nodeelse:p.lchild = new_nodedef delete(self, root, data):  # 刪除flag, n, p = self.search(root, root, data)  # n待刪除節點，p節點n的父節點if flag is False:print("無該關鍵字，刪除失敗")else:if n.lchild is None:  # n的左子樹為空（僅存在右子樹）if n == p.lchild:  # n為p的左孩子p.lchild = n.rchildelse:  # n為p的右孩子p.rchild = n.rchilddel nelif n.rchild is None:  # 右子樹為空if n == p.lchild:p.lchild = n.lchildelse:p.rchild = n.lchilddel nelse:  # n的左右子樹均不為空，將右子樹的最小數據代替此節點的數據pre = n.rchildif pre.lchild is None:  # 左子樹，則該節點為最小節點n.data = pre.datan.rchild = pre.rchilddel preelse:next = pre.lchildwhile next.lchild is not None:pre = nextnext = next.lchildn.data = next.datapre.lchild = next.rchilddel nextdef preOrderTraverse(self, node):  # 先序遍歷if node is not None:print(node.data)self.preOrderTraverse(node.lchild)self.preOrderTraverse(node.rchild)def inOrderTraverse(self, node):  # 中序遍歷if node is not None:self.inOrderTraverse(node.lchild)print(node.data)self.inOrderTraverse(node.rchild)def postOrderTraverse(self, node):  # 后序遍歷if node is not None:self.postOrderTraverse(node.lchild)self.postOrderTraverse(node.rchild)print(node.data)

層次遍歷

將二叉樹的節點加入隊列，出隊的同時，將其非空左右孩子依次入隊
出隊至隊列為空則完成遍歷

def PrintFromTopToBottom(self, root):outList=[]queue=[root]while queue!=[] and root:outList.append(queue[0].val)if queue[0].left!=None:queue.append(queue[0].left)if queue[0].right!=None:queue.append(queue[0].right)queue.pop(0)return outList

def printFromTopToBottom(self, root):if not root:return[]currentStack = [root]outList = []while currentStack:nextStack = []for point in currentStack:if point.lchild:nextStack.append(point.lchild)if point.rchild:nextStack.append(point.rchild)outList.append(point.data)currentStack = nextStackreturn outList

2.2 堆

堆樹的定義
完全二叉樹
堆樹中某個節點的值總是不大于或者不小于其孩子節點的值
堆樹中的每個節點的子樹都是堆樹

實現一個小頂堆、大頂堆、優先級隊列

實現堆排序

def heap_sort(lists):# 堆排序（交換堆頂元素和末尾元素，逐步得到最終結果）size = len(lists)build_heap(lists, size)for i in range(0, size)[::-1]:lists[0], lists[i] = lists[i], lists[0]adjust_heap(lists, 0, i)return listsdef adjust_heap(lists, i, size):# 調整堆（根結點 < 孩子結點，和最大的孩子結點交換位置）lchild = 2 * i + 1rchild = 2 * i + 2maxi = iif lchild < size and lists[maxi] < lists[lchild]:maxi = lchildif rchild < size and lists[maxi] < lists[rchild]:maxi = rchildif maxi != i:# 如果做了堆調整則maxi的值等于左節點或者右節點的，這個時候做對調值操作lists[maxi], lists[i] = lists[i], lists[maxi]adjust_heap(lists, maxi, size)def build_heap(lists, size):# 堆的構建for i in range(int(size / 2), 0, -1):adjust_heap(lists, i, size)

利用優先級隊列合并 K 個有序數組

求一組動態數據集合的最大 Top K

2.3 對應的 LeetCode 練習題

翻轉二叉樹

class Solution:def invertTree(self, root):if not root:return rootself.invertTree(root.left)self.invertTree(root.right)root.left, root.right = root.right, root.leftreturn root

二叉樹的最大深度

class Solution(object):def maxDepth(self, root):depth = 0level = [root] if root else []while level:depth += 1queue = []for el in level:if el.left:queue.append(el.left)if el.right:queue.append(el.right)level = queuereturn depth

驗證二叉查找樹

class Solution:def isValidBST(self, root, left=None, right=None):if not root:return Trueif left and left.val >= root.val:return Falseif right and right.val <= root.val:return Falsereturn self._isValidBST(root.left, left, root) and self._isValidBST(root.right, root, right)

路徑總和

class Solution:def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""if root is None:return Falseif sum == root.val and root.left is None and root.right is None:return Truereturn self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

3. 參考鏈接

https://shimo.im/docs/g9fwoinJO8cHWgUr/read