# Python3刷题系列（九）

1，Leetcode-230

2，Leetcode-208

3，Leetcode-785

4，Leetcode-144

5，Leetcode-513

6，Leetcode-684

7，Leetcode-207

8，Leetcode-110

1，Leetcode-230:

``` # leetcode-230:二叉搜索树，中序遍历，beats 56.14%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
self.cnt, self.val = 0, 0
self.inOrder(root, k)
return self.val

def inOrder(self, root: TreeNode, k: int):
if not root:
return
self.inOrder(root.left, k)
self.cnt += 1
if self.cnt == k:
self.val = root.val
return
self.inOrder(root.right, k)```

2，Leetcode-208:

```# leetcode-208： 字典树，前缀树，beats 39.87%
class Node:
def __init__(self):
self.children = {}
self.is_leaf = False

class Trie:

def __init__(self):
"""
"""
self.root = Node()

def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for c in word:
if c not in node.children:
node.children[c] = Node()
node = node.children[c]
node.is_leaf = True

def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_leaf

def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)```

3，Leetcode-785:

```# leetcode-785：二分图：beats 80.75%
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
colors = [-1] * len(graph)
for i in range(len(graph)):
if colors[i] == -1 and not self.dfs(i, 0, colors, graph):
return False
return True

def dfs(self, cur_node, cur_color, colors, graph):
if colors[cur_node] != -1:
return colors[cur_node] == cur_color

colors[cur_node] = cur_color
for next_node in graph[cur_node]:
if not self.dfs(next_node, 1-cur_color, colors, graph):
return False
return True```

4，Leetcode-144:

```# leetcode-144：二叉树前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:  # 递归写法，beats 12.29%
def preorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if not root:
return result
result.append(root.val)
result += self.preorderTraversal(root.left)
result += self.preorderTraversal(root.right)
return result

class Solution:  # 非递归写法，beats 84.21%
def preorderTraversal(self, root: TreeNode) -> List[int]:
result = []
s = []
if not root:
return result
s.append(root)
while s:
root = s.pop()
result.append(root.val)
if root.right:
s.append(root.right)
if root.left:
s.append(root.left)
return result```

5，Leetcode-513:

```# leetcode-513：查找树的左下角值，beats  88.92%
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
q = [root]
while q:
root = q.pop(0)
if root.right:
q.append(root.right)
if root.left:
q.append(root.left)
return root.val```

6，Leetcode-684------并查集

```# leetcode-684：并查集，beats  5.42%
class UnionFind:
def __init__(self, n):
self.ids = []
for i in range(n+1):
self.ids.append(i)

def union(self, u, v):
u_id = self.find(u)
v_id = self.find(v)
if u_id == v_id:
return
for i in range(len(self.ids)):
if self.ids[i] == u_id:
self.ids[i] = v_id

def find(self, p):
return self.ids[p]

def connect(self, u, v):
return self.find(u) == self.find(v)

class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
uf = UnionFind(len(edges))
for e in edges:
u, v = e[0], e[1]
if uf.connect(u, v):
return u, v
uf.union(u, v)
return -1, -1```

7，Leetcode-207:

```# leetcode-207：拓扑排序，beats 90.89%
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graphic = [[] for i in range(numCourses)]
for pre in prerequisites:
graphic[pre[0]].append(pre[1])
visited = [0]*numCourses
for i in range(numCourses):
if self.exist_cycle(visited, graphic, i):
return False
return True

def exist_cycle(self, visited, graphic, cur_node):
if visited[cur_node] == 1:
return True
if visited[cur_node] == 2:
return False
visited[cur_node] = 1
for next_node in graphic[cur_node]:
if self.exist_cycle(visited, graphic, next_node):
return True
visited[cur_node] = 2
return False```

8，Leetcode-110:

```# leetcode-110：平衡二叉树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:  # beats 19.84%
def isBalanced(self, root: TreeNode) -> bool:
if root is None:
return True
left_height = self.getHeight(root.left)
right_height = self.getHeight(root.right)
if abs(left_height - right_height) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)

def getHeight(self, root: TreeNode) -> int:
if root is None:
return 0
left_height = self.getHeight(root.left)
right_height = self.getHeight(root.right)
return max(left_height, right_height) +1

class Solution:  # 这个解决方案的逻辑错误点在哪？
def _maxDepth(self, node: TreeNode) -> int:
if (not node):
return 0
left_depth = self._maxDepth(node.left)
right_depth = self._maxDepth(node.right)
return max(left_depth, right_depth) + 1

def _minDepth(self, node: TreeNode) -> int:
if (not node):
return 0
left_depth = self._minDepth(node.left)
right_depth = self._minDepth(node.right)
return min(left_depth, right_depth) + 1

def isBalanced(self, root: TreeNode) -> bool:
return (self._maxDepth(root) - self._minDepth(root)) <= 1```

0 条评论

• ### 【算法基础】java 排序算法

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大...

用户认证接口：根据客户端IP和port，进行IP反查和端口范围确认，如符合则用户认证通过。 当前使用的是Nginx负载均衡，从客户端到Nginx端 ip和po...

• ### 安卓求职者的秋招总结，感谢牛客网，感谢牛友们

楼主秋招投的是安卓岗，今年安卓确实比较好找工作，就我来说吧，给了面试机会的基本都拿到offer了（可见面的不多），知名一点的是网易，美团，头条，还有两个是贝壳，...

• ### handler模块(100%)

相信大家在看了前一章的模块概述以后，都对nginx的模块有了一个基本的认识。基本上作为第三方开发者最可能开发的就是三种类型的模块，即handler，filter...

• ### NGINX 配置文件 fastcgi_pass

语法：fastcgi_pass fastcgi-server 默认值：none 使用字段：http, server, location 指定FastCGI...

• ### 面试官：mybatis你只写了接口为啥就能执行sql啊？

又是一年毕业季，很多小伙伴开始去大城市打拼。来大城市第一件事就是租房，免不了和中介打交道，因为很多房东很忙，你根本找不到他。从这个场景中就可以抽象出来代理模式

• ### Java：前程似锦的 NIO 2.0

Java 之所以能够霸占编程语言的榜首，其强大、丰富的类库功不可没，几乎所有的编程问题都能在其中找到解决方案。但在早期的版本当中，输入输出（I/O）流并不那么令...

• ### 001.RAID简介

独立磁盘冗余数组（RAID, Redundant Array of Independent Disks），旧称廉价磁盘冗余数组（RAID,Redundant A...