Python数据结构之图与二叉查找树_python数据结构图和查找

目录

1. 图的基础知识
2. 图的深度优先搜索与宽度优先搜索
3. 课程安排 (LeetCode 207,210,630)
4. 最小高度的树 (LeetCode 310)
5. 二叉查找(排序)树的基础知识
6. 二叉查找树中的第K小的数(LeetCode 230)
7. 二叉查找树编码与解码(LeetCode 449)
8. 逆序数 (LeetCode 315)

1. 图的基础知识

图是算法中最强大的框架之一，树结构只是图的一种特殊情况。图可以通过邻接表和加权邻接字典表示

2. 图的深度优先搜索与宽度优先搜索

参考 https://www.cnblogs.com/yupeng/p/3414736.html这篇博客

2.1深度优先算法：

（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。

2.2宽度优先算法：

（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。

3. 课程安排 (LeetCode 207,210,630)

3.1题目

• LeetCode 207 Course Schedule
  There are a total of n courses you have to take, labeled from 0 to n - 1.
  Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
  Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
  For example:

  2, [[1,0]]
  1

  There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

  2, [[1,0],[0,1]]
  1

  There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

• LeetCode 210 Course Schedule II
  There are a total of n courses you have to take, labeled from 0 to n - 1.
  Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
  Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
  There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
  For example:

  2, [[1,0]]
  1

  There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

  4, [[1,0],[2,0],[3,1],[3,2]]
  1

  There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

• LeetCode 630 Course Schedule III
  There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
  Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
  Example:

  Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
  Output: 3
  Explanation: 
  There're totally 4 courses, but you can take 3 courses at most:
  First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
  Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
  Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
  The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.
  1
  2
  3
  4
  5
  6
  7
  8

3.2思路

• LeetCode 207 Course Schedule
  相当于判断有向图中有无环的存在
  如果存在环则返回false
• LeetCode 210 Course Schedule II
  要完成所有课程，返回所有上课的顺序
  （1）初始化一个大小为numCorset的数组grap
  （2）将图中的节点的入度保存到数组中，将数组中第一个入度为0的节点找出，并设为-1，数组中所有以该顶点为入度的顶点入度减1，将其push到结果数组中
  （3）重复（2）numCourse次，若期间未找到入度为0 的顶点，返回空。
• LeetCode 630 Course Schedule III
  根据课程的结束时间对课程进行排序
  遍历课程，利用优先队列（heapq）维护当前满足最迟完成时间约束的课程时长，弹出不满足约束条件的课程时长（先弹出课程时间较长的课程，这样可以使得课程的真实结束时间尽量早）
  返回优先队列的长度。
  约束条件：时间间隔$\leq end$

3.3代码

• LeetCode 207 Course Schedule

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        node = [[] for i in range(numCourses)]
        visit = [0 for i in range(numCourses)]
        for x, y in prerequisites:
            node[x].append(y)
        def dfs(i):
            if visit[i] == -1:
                return False
            if visit[i] == 1:
                return True
            visit[i] = -1
            for j in node[i]:
                if not dfs(j):
                    return False
            visit[i] = 1
            return True
        for i in range(numCourses):
            if not dfs(i):
                return False
        return True
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

• LeetCode 210 Course Schedule II

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        grap = [0] * numCourses
        for pre in prerequisites:
            grap[pre[0]] += 1
        ans =[]
        for j in range(numCourses):
            for i in range(numCourses):
                if grap[i] == 0:
                    ans.append(i)
                    grap[i] = -1
                    for pre in prerequisites:
                        if pre[1] == i:
                            grap[pre[0]] -= 1
                    break
        if len(ans) != numCourses:
            return []
        else:
            return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• LeetCode 630 Course Schedule III

import heapq
class Solution(object):
    def scheduleCourse(self, courses):
        """
        :type courses: List[List[int]]
        :rtype: int
        """
        heap = []
        start = 0
        courses = sorted(courses, key=lambda x: x[1])
        for t, end in courses:
            start += t
            heapq.heappush(heap, -t)
            while start > end:
                start += heapq.heappop(heap)
        return len(heap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4. 最小高度的树 (LeetCode 310Minimum Height Trees)

4.1题目

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
   / \
  2   3
1
2
3
4
5

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

 0  1  2
  \ | /
    3
    |
    4
    |
    5
1
2
3
4
5
6
7

return [3, 4]

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

4.2思路

先计算每个点的度，然后将度为1的点放入list或queue中进行计算，把这些点从neighbor中去除，然后计算接下来degree=1的点，最后剩下1-2点（因为能成为答案的点一定在叶结点的上一层）就是root

4.3代码

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1:
            return [0]
        edge_dict = {}
        degree = [0] * n
        for i, j in edges:
            edge_dict[i] = edge_dict.get(i, []) + [j]
            edge_dict[j] = edge_dict.get(j, []) + [i] 
            degree[i] += 1
            degree[j] += 1
        degree_1 = []
        for i in range(n):
            if degree[i] == 1:
                degree_1.append(i)
        while n > 2:
            n -= len(degree_1)
            dq = []
            for i in degree_1:
                out = edge_dict[i][0]
                edge_dict[out].remove(i)
                if len(edge_dict[out]) <= 1:
                    if out not in dq:
                        dq.append(out)
            degree_1 = dq[:]
        return degree_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

5. 二叉查找(排序)树的基础知识

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

6. 二叉查找树中的第K小的数(LeetCode 230Kth Smallest Element in a BST)

6.1题目

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

6.2思路

根据二叉查找树的特点，使用递归方法按先序遍历的方法遍历数，直到遍历到第k个节点。

6.3代码

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.k = k
        self.ans = None
        self.solve(root)
        return self.ans

    def solve(self, root):
        if not root:
            return
        self.solve(root.left)
        self.k -= 1
        if self.k == 0:
            self.ans = root.val
            return 
        self.solve(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7. 二叉查找树编码与解码(LeetCode 449 Serialize and Deserialize BST)

7.1题目

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

7.2思路

序列化：先序遍历二叉搜索树，输出逗号分隔值字符串
反序列化：利用栈和节点站保存重建二叉树过程中的节点，最大值栈rstack保存当前节点的右节点允许的最大值，遍历序列化串，记当前数值为val，新增树节点node=TreeNode（val）
若val

7.3代码

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        ans = str(root.val)
        if left:
            ans += ',' + left
        if right:
            ans += ',' + right
        return ans


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        nstack, rstack = [], [0x7FFFFFFF]
        for val in map(int, data.split(',')):
            node = TreeNode(val)
            if nstack:
                if val < nstack[-1].val:
                    nstack[-1].left = node
                    rstack.append(nstack[-1].val)
                else:
                    while val > rstack[-1]:
                        while nstack[-1].val > nstack[-2].val:
                            nstack.pop()
                        nstack.pop()
                        rstack.pop()
                    nstack[-1].right = node
            nstack.append(node)
        return nstack[0]
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
39
40
41
42
43
44

8. 逆序数 (LeetCode 315 Count of Smaller Numbers After Self)

8.1题目

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
1
2
3
4
5
6

8.2思路

建立二叉搜索树，从根节点开始插入，计算比自身值小的节点数

8.3代码

class BinarySearchTreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.count = 1
        self.leftTreeSize = 0


class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def insert(self, val, root):
        if not root:
            self.root = BinarySearchTreeNode(val)
            return 0

        if val == root.val:
            root.count += 1
            return root.leftTreeSize

        if val < root.val:
            root.leftTreeSize += 1

            if not root.left:
                root.left = BinarySearchTreeNode(val)
                return 0
            return self.insert(val, root.left)

        if not root.right:
            root.right = BinarySearchTreeNode(val)
            return root.count + root.leftTreeSize

        return root.count + root.leftTreeSize + self.insert(
            val, root.right)

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tree = BinarySearchTree()
        return [
            tree.insert(nums[i], tree.root)
            for i in xrange(len(nums) - 1, -1, -1)
        ][::-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
39
40
41
42
43
44
45
46
47
48