常见二叉树

  • 1.满二叉树
    满二叉树最大的特点： 假设深度是h，那么总节点就是2^h-1
  • 2.完全二叉树
  • 3.二叉搜索树
    二叉搜索树BST，对于树的每个节点，其左子树的每个节点都小于这个值，右子树的每个几点都大于这个节点值：左下右大！

二叉树的实现方式

1
2
3
4
5
6
7
8
9
class TreeNode:
    def __init__(self,x,left,right)
        self.value = x
        self.left = Node
        self.right= Node

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

二叉树的递归遍历[DFS]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class TreeNode:
    def __init__(self,x,left,right)
        self.value = x
        self.left = Node
        self.right= Node

# 二叉树的遍历框架(DFS)
def traverse(root:TreeNode):
    if root is Node:
        return 
    # 前序位置
    traverse(root.left)
    # 中序位置
    traverse(root.right)
    # 后续位置

二叉树的层序遍历[BFS]

BFS写法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

from binaryTree.node import TreeNode

"""
  二叉树的层序遍历，又称之为BFS
"""

class Solution:
    def bfs(self, root):
        if not root:
            return []
        result = []
        queue = [root]
        while queue:
            level_values = []
            level_size = len(queue)
            for i in range(level_size):
                node = queue.pop(0)
                level_values.append(node.value)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level_values)
        return result


if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(7)
    s = Solution()
    print(s.bfs(root))  # [[1], [2, 3], [4, 5, 6, 7]]

BFS写法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    while q:
        cur = q.popleft()
        # 访问 cur 节点
        print(cur.val)

        # 把 cur 的左右子节点加入队列
        if cur.left is not None:
            q.append(cur.left)
        if cur.right is not None:
            q.append(cur.right)

例题： 查找二叉树的最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.minDepthValue = 10000
        self.currentDepth = 0

    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        self.traverse(root)
        return self.minDepthValue

    def traverse(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        self.currentDepth += 1
        if root.left is None and root.right is None:
            self.minDepthValue = min(self.minDepthValue, self.currentDepth)
        self.traverse(root.left)
        self.traverse(root.right)
        self.currentDepth -= 1
        return self.minDepthValue

二叉树系列算法核心纲领

二叉树的解题思路

  • 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个traverse函数函数陪外部变量实现，遍历的思维模式。
  • 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，分解问题的思维模式
    无论是哪种思维模式，都需要思考：
    如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？ 其他的节点不用操心，递归函数会在所有节点上执行相同的操作。

二叉树的重要性

比如，经典排序算法： 快速排序和归并排序，有什么理解？
快速排序就是个二叉树的前序遍历，归并排序就是二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
""""
   对于快速排序， 若在nums[lo..hi]排序，我们先找一个分界点p, 通过交换元素使得 nums[lo..p-1]都要小于等于nums[p],
   且nums[p+1..hi]都大于nums[p], 然后递归nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点
"""
def sort(nums: list, lo: int, hi: int):
    if lo>= hi:
       return
    # ************************
    # 通过交换元素构建分界点 p
    p = partition(nums, lo, hi)
    sort(nums, lo, p-1)
    sort(nums, p+1, hi)


def partition(arr, low, high):
    i = (low - 1) 
    pivot = arr[high]  

    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)
  • 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sort(nums: List[int], lo: int, hi: int) -> None:
    # 定义：排序 nums[lo..hi]
    mid = (lo + hi) // 2
    # 排序 nums[lo..mid]
    sort(nums, lo, mid)
    # 排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi)

    # ****** 后序位置 ******
    # 合并 nums[lo..mid] 和 nums[mid+1..hi]
    merge(nums, lo, mid, hi)
    # *********************


__END__