题目链接:https://leetcode.com/problems/minimum-height-trees
解法:
这个题类似最短路径问题,用的BFS。
从题目的例子可以看到,最小高度树的根节点,好像是入度比较大的节点,这是一个大概的认识。
为了找到这些点,我们从边缘开始,先找到所有出度为1的节点,然后把所有出度为1的节点进队列,以它们为包围圈,不断地BFS,最后找到的就是两边同时向中间靠近的节点。
那么相比于从一端到另一端,从中间到一端的路径肯定更短。所以BFS结束后,就找到了最小高度树的根节点。
参考题解:BFS
边界条件:
时间复杂度:O(n),其中?n?是为节点的个数
空间复杂度:O(n),其中?n是为节点的个数
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
res = []
# 记录每个点的入度
degree = [0] * n
# 存储邻接节点
adjacency = defaultdict(list)
for edge in edges:
degree[edge[0]] += 1
degree[edge[1]] += 1
adjacency[edge[0]].append(edge[1])
adjacency[edge[1]].append(edge[0])
# 把入度为1的节点加入列表
que = deque()
for i in range(n):
if degree[i] == 1:
que.append(i)
# 一次性遍历入度为1的节点(叶子结点),把这层叶子结点删除后新的叶子结点加入队列
while que:
# 每一轮都更新最小高度树
res = []
size = len(que)
for i in range(size):
cur = que.popleft()
res.append(cur)
neighbors = adjacency[cur]
# cur 从队列拿出来,那就不存在了,所以相邻节点的入度减1
for neighbor in neighbors:
degree[neighbor] -= 1
# 如果变成了叶子结点,那么加入队列
if degree[neighbor] == 1:
que.append(neighbor)
# 最后返回的叶子节点,就是最小高度树的节点
return res
题目链接:https://leetcode.com/problems/word-ladder
解法:
单词列表可以转化为无向图,只要一个字母不同的单词之间是相邻的。
那么这个题转化为无向图中两个顶点之间的最短路径的长度,可以通过广度优先遍历得到。
参考的题解中,考虑到无向图没有直接给出,如果构建为邻接表就需要对单词进行两两比较,时间复杂度较高,于是没有构建邻接表。替换方案是:在遍历队列元素时,通过把单词的某个字符替换为26个字母中的一个,并且替换后的单词需要在word_list里面,这样的替换单词就是相邻节点。
参考题解:BFS
边界条件:
时间复杂度:
空间复杂度:
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
que = deque([beginWord])
visited = set([beginWord])
# 变换后的长度是一样的
word_len = len(beginWord)
# 每一轮遍历,那么路径加1
step = 1
while que:
step += 1
size = len(que)
for i in range(size):
word = que.popleft()
word_list = list(word)
# 对于word中的一个字符进行替换
for j in range(word_len):
raw_char = word_list[j]
for k in range(26):
word_list[j] = chr(ord('a')+k)
# 替换一个字符后的word
next_word = ''.join(word_list)
if next_word in word_set:
if next_word == endWord:
return step
if next_word not in visited:
que.append(next_word)
visited.add(next_word)
# 还原该位置的字符,继续替换另一个位置的
word_list[j] = raw_char
return 0
题目链接:https://leetcode.com/problems/kth-smallest-element-in-a-bst
解法:
二叉搜索树具有一个重要性质:二叉搜索树的中序遍历为递增序列。
本题可被转化为求中序遍历的第?k个节点,那么我们不用遍历所有的节点,只需要在遍历过程中同时记录节点个数,个数为k时就返回节点的值。
参考题解:中序遍历
边界条件:
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.res = 0
# 这个k必须是全局变量,一直在减小,而不是可以回溯的,所以不能作为dfs的形参
self.k = k
self.dfs(root)
return self.res
def dfs(self, root):
if not root: return
# 处理左,一直深入到叶子节点才返回
self.dfs(root.left)
# 处理中,剪枝的操作
if self.k == 0: return
self.k -= 1
if self.k == 0:
self.res = root.val
# 处理右
self.dfs(root.right)