leetcode-hot100树的专题
230.二叉搜索树中的第K小的元素
题目链接
230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）
解题思路
# 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:def dfs(cur):result = left = right = []if cur == None:return []return dfs(cur.left)+[cur.val]+dfs(cur.right)result = dfs(root)return result[k - 1]199.二叉树的右视图
题目链接
199. 二叉树的右视图 - 力扣（LeetCode）
解题代码
class Solution:def rightSideView(self, root: TreeNode) -> List[int]:rightmost_value_at_depth = dict() # 深度为索引，存放节点的值max_depth = -1stack = [(root, 0)]while stack:node, depth = stack.pop()if node is not None:# 维护二叉树的最大深度max_depth = max(max_depth, depth)# 如果不存在对应深度的节点我们才插入rightmost_value_at_depth.setdefault(depth, node.val)stack.append((node.left, depth + 1))stack.append((node.right, depth + 1))return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]