三个月算法进阶--day42
目录
第k个最小元素
假设k总是有效的，1 <= k <= 元素个数
二叉搜索树/二叉查找树
左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。
查询效率高于链表结构。
前序遍历、中序遍历、后序遍历
深度优先搜索DFS
preorder: [root.val] + preorder(root.left) + preorder(root.right)
inorder: Left -> Node -> Right
postorder: Left -> Right -> Node
BST的中序遍历是升序序列
记录
leetcode第230题二叉搜索树中第K小的元素
递归
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
def indoor(r):
return indoor(r.left) + [r.val] + indoor(r.right) if r else []
return indoor(root)[k-1]
迭代
class Solution:
def KthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
时间复杂度和空间复杂度是O(H + k)，当树是一个平衡树时，复杂度是O(log N + k)，当树是一个不平衡树时，复杂度是O(N + k)，此时所有的节点都在左子树。
递归剪枝，防止过度遍历
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
self.num = 0
self.res = 0
def dfs(root):
if not root:
return
dfs(root.left)
self.num += 1
if self.num == k:
self.res = root.val
return
dfs(root.right)
dfs(root)
return self.res
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
def inorder(root: TreeNode) -> List[int]:
if root:
yield from inorder(root.left)
yield root.val
yield from inorder(root.right)
for n, val in enumerate(inorder(root)):
if n == k - 1:
return val