⚡二叉树基础认知
二叉树是数据结构中最基础且核心的非线性结构之一,由有限个节点构成的集合,该集合满足以下条件:
- 每个节点最多有两棵子树,分别称为左子树与右子树
- 左子树与右子树有严格的顺序性,不能任意颠倒
- 二叉树可以为空集,此时称为空树
与树不同,二叉树的每个节点最多仅有两个子节点,且子节点位置固定。这种结构特性使其在算法设计、编译器实现、数据库索引等领域具有广泛应用。
在Python中,二叉树节点通常用类表示:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
这种定义方式简洁明了,符合Python面向对象设计哲学。其中:
val存储节点值,可为任意可哈希对象left与right分别指向左右子节点,为空时设为None
值得注意的是,Python标准库并未内置二叉树结构,需开发者自行实现。这也使得二叉树成为学习算法与数据结构的理想载体——既不过于复杂,又能充分展现递归、迭代、内存管理等核心编程思想。
从计算机科学教育角度看,二叉树是连接基础编程与高级算法的桥梁。例如,在学习递归时,二叉树的遍历(前序、中序、后序)是经典案例;在理解动态规划时,树形DP问题常以二叉树为载体;在掌握图算法时,二叉搜索树(BST)又是图论与树结构的交汇点。
更进一步地,二叉树的变体(如平衡二叉树、红黑树、AVL树)构成了现代数据库索引与操作系统内存管理的理论基础。例如,MySQL的InnoDB引擎使用B+树(二叉树的推广)实现聚簇索引;Linux内核的CFS调度器使用红黑树管理进程控制块;而Python的dict与set底层虽采用哈希表,但在某些版本中也引入了树结构优化内存布局。
因此,深入掌握二叉树不仅有助于通过技术面试,更是构建扎实计算机科学知识体系的关键一步。
〔二叉树的数学定义〕
形式化地,二叉树可递归定义为:
二叉树是n(n≥0)个节点的有限集合,该集合或为空树(n=0),或由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
该定义强调了二叉树的递归特性——任何子树本身仍是二叉树。这一特性为递归算法设计提供了理论基础,例如:
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
上述代码计算二叉树高度,其时间复杂度为O(n),空间复杂度(递归栈)为O(h),其中h为树高。
〔二叉树的存储结构〕
二叉树主要有两种存储方式:
- 链式存储:如上述
TreeNode类,通过指针连接节点。优点是灵活高效,适用于动态插入删除;缺点是访问子节点需遍历指针,缓存局部性较差。 - 顺序存储:用数组存储节点,下标关系满足:
- 父节点下标i的左子节点为2i+1,右子节点为2i+2
- 子节点下标i的父节点为floor((i-1)/2)
顺序存储适用于完全二叉树(如堆结构),可避免指针开销;但对稀疏树结构会造成大量空间浪费。例如,高度为h的单支树(所有节点只有左子节点)在顺序存储中需2h-1个数组位置,而实际仅用h个节点。
〔二叉树的基本性质〕
二叉树具有以下重要性质:
- 第i层最多有2i-1个节点(i≥1)
- 高度为h的二叉树最多有2h-1个节点
- 对任意二叉树,叶子节点数n0与度为2的节点数n2满足:n0 = n2 + 1
- 完全二叉树的节点数n与高度h满足:h = floor(log2n) + 1
这些性质为算法复杂度分析提供理论依据。例如,平衡二叉树的高度为O(log n),使得查找、插入、删除等操作的时间复杂度可控制在O(log n)内。
〔二叉树 vs 二叉搜索树〕
需特别注意:二叉树是通用数据结构,而二叉搜索树(Binary Search Tree, BST)是满足特定性质的二叉树:
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树也均为二叉搜索树
该性质使BST支持O(log n)时间复杂度的查找操作(在平衡前提下),成为动态集合的高效实现方式。
⚙️二叉树构建方法
构建二叉树是学习数据结构的入门实践。根据输入形式不同,常见构建方式包括:
〔1. 层次遍历构建〕
输入为层次遍历序列(如[1,2,3,None,4]),常用于LeetCode题目:
from collections import deque
def build_tree_from_level_order(nodes):
if not nodes or nodes[0] is None:
return None
root = TreeNode(nodes[0])
queue = deque([root])
i = 1
while queue and i < len(nodes):
node = queue.popleft()
if i < len(nodes) and nodes[i] is not None:
node.left = TreeNode(nodes[i])
queue.append(node.left)
i += 1
if i < len(nodes) and nodes[i] is not None:
node.right = TreeNode(nodes[i])
queue.append(node.right)
i += 1
return root
该算法时间复杂度为O(n),空间复杂度为O(w),其中w为树的最大宽度。适用于完全二叉树及完全不二叉树的构建。
〔2. 前序+中序构建〕
已知前序遍历与中序遍历可唯一确定一棵二叉树:
def build_tree_pre_in(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = build_tree_pre_in(preorder[1:mid+1], inorder[:mid])
root.right = build_tree_pre_in(preorder[mid+1:], inorder[mid+1:])
return root
关键点在于中序序列中根节点位置将序列分为左右子树,前序序列中根节点后紧跟左子树节点。时间复杂度O(n2)(因index操作),可优化为O(n)(用哈希表预存中序索引)。
〔3. 后序+中序构建〕
类似地,后序序列末尾为根节点:
def build_tree_post_in(postorder, inorder):
if not postorder or not inorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = build_tree_post_in(postorder[:mid], inorder[:mid])
root.right = build_tree_post_in(postorder[mid:-1], inorder[mid+1:])
return root
构建过程体现了递归思想的核心——将大问题分解为规模更小的同类子问题。
〔4. 手动构建典型示例〕
以下构建一棵典型二叉搜索树:
root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(6)
root.left.right.left = TreeNode(4)
root.left.right.right = TreeNode(7)
root.right.right = TreeNode(14)
root.right.right.left = TreeNode(13)
该树结构如下:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
此结构是后续所有算法实现的基础,建议读者亲手绘制并验证遍历结果。
〔5. 复杂场景:带父指针的二叉树〕
某些算法(如后序遍历的迭代实现)需父节点引用:
class TreeNodeWithParent:
def __init__(self, val=0, left=None, right=None, parent=None):
self.val = val
self.left = left
self.right = right
self.parent = parent
构建时需同步设置父指针,例如:
root = TreeNodeWithParent(1)
root.left = TreeNodeWithParent(2, parent=root)
root.right = TreeNodeWithParent(3, parent=root)
root.left.left = TreeNodeWithParent(4, parent=root.left)
此类设计在树路径回溯、 Lowest Common Ancestor(LCA)等算法中非常实用。
🔍二叉树遍历算法
遍历是二叉树操作的基础,分为递归与非递归两种实现方式。根据访问顺序不同,可分为:
〔1. 递归遍历〕
递归遍历最符合人类思维,代码简洁清晰:
# 前序遍历:根 → 左 → 右
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# 中序遍历:左 → 根 → 右
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
# 后序遍历:左 → 右 → 根
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
递归遍历的时间复杂度为O(n),空间复杂度为O(h)(递归栈深度)。对平衡树为O(log n),对单支树为O(n)。
〔2. 迭代遍历〕
迭代遍历避免递归调用开销,需显式使用栈:
def preorder_iterative(root):
if not root:
return []
stack, result = [root], []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
关键点:先压入右子节点,再压入左子节点,确保左子节点先出栈。
def inorder_iterative(root):
stack, result = [], []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
中序遍历需模拟“最左节点”路径,利用栈暂存路径节点。
def postorder_iterative(root):
if not root:
return []
stack, result = [root], []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
后序遍历可反向思维:根→右→左的逆序即左→右→根。此技巧显著简化实现。
〔3. Morris遍历〕
Morris遍历是空间复杂度O(1)的遍历方法,通过临时修改树结构实现:
def morris_inorder(root):
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if not pre.right:
pre.right = current
current = current.left
else:
pre.right = None
result.append(current.val)
current = current.right
return result
Morris遍历的核心是“线索化”——临时将前驱节点的右指针指向当前节点。虽然修改了树结构,但遍历完成后恢复原状,不影响后续操作。该方法适用于内存受限场景,如嵌入式设备。
〔4. 层序遍历(BFS)〕
层序遍历使用队列实现,按层级访问节点:
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
该算法可进一步扩展为“之字形层序遍历”(Zigzag Level Order),通过奇偶层反转实现:
def zigzag_level_order(root):
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
level = deque()
for _ in range(level_size):
node = queue.popleft()
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(list(level))
left_to_right = not left_to_right
return result
此变体常用于可视化树结构,增强层次感。
〔5. 遍历应用实例〕
遍历是许多树算法的基础,例如:
- 求最大深度:后序遍历中取左右子树深度最大值+1
- 验证二叉搜索树:中序遍历结果应严格递增
- 路径求和:前序遍历中累加路径值,叶节点判断是否满足条件
- 对称二叉树:中序遍历结果应为回文串(需结合其他条件)
这些应用体现了遍历作为“操作骨架”的核心地位。
🌳二叉搜索树(BST)详解
二叉搜索树(Binary Search Tree, BST)是满足以下性质的二叉树:
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树也均为二叉搜索树
该性质使BST支持高效查找、插入、删除操作(平均O(log n)时间复杂度),是动态集合的首选数据结构。
〔1. BST基础操作〕
查找操作:
def search_bst(root, target):
if not root or root.val == target:
return root
if target < root.val:
return search_bst(root.left, target)
return search_bst(root.right, target)
时间复杂度O(h),h为树高。对平衡BST为O(log n),对单支树为O(n)。
插入操作:
def insert_bst(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
插入位置唯一,即保持BST性质的叶节点位置。
删除操作:
def delete_bst(root, key):
if not root:
return root
if key < root.val:
root.left = delete_bst(root.left, key)
elif key > root.val:
root.right = delete_bst(root.right, key)
else:
# 三种情况:无子节点、单子节点、双子节点
if not root.left:
return root.right
if not root.right:
return root.left
# 双子节点:找右子树最小值替代
min_larger = root.right
while min_larger.left:
min_larger = min_larger.left
root.val = min_larger.val
root.right = delete_bst(root.right, min_larger.val)
return root
删除双子节点时,需找到右子树最小值(或左子树最大值)替代根节点,确保BST性质不变。
〔2. BST验证〕
验证一棵树是否为BST,中序遍历法最直观:
def is_bst(root):
def inorder(node, prev):
if not node:
return True, prev
left_valid, prev = inorder(node.left, prev)
if not left_valid or (prev is not None and node.val <= prev):
return False, node.val
return inorder(node.right, node.val)
return inorder(root, None)[0]
更优方法是递归验证每个节点值是否在有效范围内:
def is_bst_range(root, min_val=float('-inf'), max_val=float('inf')):
if not root:
return True
if not (min_val < root.val < max_val):
return False
return (is_bst_range(root.left, min_val, root.val) and
is_bst_range(root.right, root.val, max_val))
该方法避免了中序遍历的额外空间开销,时间复杂度O(n),空间复杂度O(h)。
〔3. BST变体:AVL树〕
标准BST在极端情况下(如顺序插入)会退化为单支树,时间复杂度退化为O(n)。AVL树通过旋转操作维持平衡,确保树高为O(log n)。
AVL树定义:任意节点左右子树高度差不超过1。
插入操作需维护平衡因子(左高-右高),并通过以下旋转调整:
- LL旋转:左子树的左子树过高 → 右旋
- RR旋转:右子树的右子树过高 → 左旋
- LR旋转:左子树的右子树过高 → 左旋+右旋
- RL旋转:右子树的左子树过高 → 右旋+左旋
以下为LL旋转实现:
def rotate_right(y):
x = y.left
T2 = x.right
# 旋转
x.right = y
y.left = T2
# 更新高度
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
AVL树的旋转操作是理解平衡树的核心,其思想被广泛应用于红黑树、伸展树等自平衡结构中。
〔4. BST应用实例〕
有序流数据处理:
class StreamChecker:
def __init__(self):
self.root = None
def add(self, val):
self.root = insert_bst(self.root, val)
def get_sorted(self):
return inorder(self.root)
该设计支持动态添加数据并获取有序序列,适用于实时排序场景。
区间查询:
def range_query(root, low, high):
if not root:
return []
result = []
if low < root.val:
result.extend(range_query(root.left, low, high))
if low <= root.val <= high:
result.append(root.val)
if high > root.val:
result.extend(range_query(root.right, low, high))
return result
该算法时间复杂度为O(k + log n),其中k为结果数量,显著优于暴力遍历。
⚖️AVL树深度解析
AVL树(Adelson-Velsky and Landis Tree)是最早被发明的自平衡二叉搜索树,其核心思想是通过旋转操作维持树的平衡性,确保任何节点的左右子树高度差不超过1。
〔1. 平衡因子定义〕
节点的平衡因子 = 左子树高度 - 右子树高度
AVL树要求所有节点的平衡因子 ∈ {-1, 0, 1}
〔2. 插入操作的四种旋转〕
LL情况(左子树过高,且插入在左子树的左侧):
右旋操作将左子节点提升为根节点:
def rotate_right(y):
x = y.left
T2 = x.right
# 旋转
x.right = y
y.left = T2
# 更新高度
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
旋转后平衡因子恢复为0。
RR情况(右子树过高,且插入在右子树的右侧):
左旋操作将右子节点提升为根节点:
def rotate_left(y):
x = y.right
T2 = x.left
# 旋转
x.left = y
y.right = T2
# 更新高度
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
LR情况(左子树过高,但插入在左子树的右侧):
先左旋左子树,再右旋整棵树:
def rotate_lr(root):
root.left = rotate_left(root.left)
return rotate_right(root)
RL情况(右子树过高,但插入在右子树的左侧):
先右旋右子树,再左旋整棵树:
def rotate_rl(root):
root.right = rotate_right(root.right)
return rotate_left(root)
〔3. 删除操作的平衡调整〕
删除操作可能导致节点失衡,需从删除位置向上检查并旋转:
def delete_avl(root, key):
# ... 删除逻辑(与BST相同)...
# 更新高度
root.height = 1 + max(get_height(root.left), get_height(root.right))
# 检查平衡因子
balance = get_balance(root)
# 四种失衡情况
if balance > 1:
if get_balance(root.left) >= 0: # LL
return rotate_right(root)
else: # LR
root.left = rotate_left(root.left)
return rotate_right(root)
if balance < -1:
if get_balance(root.right) <= 0: # RR
return rotate_left(root)
else: # RL
root.right = rotate_right(root.right)
return rotate_left(root)
return root
删除操作可能引发连续失衡,需逐层向上调整,时间复杂度O(log n)。
〔4. AVL树性能分析〕
时间复杂度:
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
由于严格平衡,AVL树性能稳定,但旋转操作开销较大。
空间复杂度:
- 每个节点需存储高度信息(额外O(1)空间)
- 递归实现需O(log n)栈空间
〔5. AVL树 vs 红黑树〕
虽然AVL树查找性能更优,但红黑树在插入/删除时旋转次数更少,因此:
- AVL树适用于查找密集型场景(如数据库索引)
- 红黑树适用于插入/删除频繁场景(如C++ STL的map/set)
Python的dict与set采用哈希表而非平衡树,但其设计思想(如碰撞处理、扩容机制)与树结构有异曲同工之妙。
🔗线索二叉树
线索二叉树通过利用空指针域存储前驱/后继信息,实现非递归遍历且无需栈空间。
〔1. 线索化原理〕
在二叉树中,n个节点共有2n个指针域:
- n-1个用于指向子节点
- n+1个为空指针
线索化将空指针域改为指向前驱或后继节点。
〔2. 线索化节点定义〕
class ThreadedNode:
def __init__(self, val=0, left=None, right=None,
lthread=True, rthread=True):
self.val = val
self.left = left
self.right = right
self.lthread = lthread # True表示left是线索
self.rthread = rthread # True表示right是线索
线索化需在遍历过程中建立线索:
def inorder_threading(root):
def inorder(node, prev):
if not node:
return prev
prev = inorder(node.left, prev)
if not node.left:
node.left = prev
node.lthread = True
if prev and not prev.right:
prev.right = node
prev.rthread = True
return inorder(node.right, node)
# 添加头节点简化操作
head = ThreadedNode()
head.left = root
head.lthread = False
if root:
prev = inorder(root, head)
prev.right = head
prev.rthread = True
return head
〔3. 线索二叉树遍历〕
中序线索二叉树的遍历无需栈:
def inorder_traversal_threaded(head):
result = []
current = head.right # 第一个节点
while current and current != head:
result.append(current.val)
if current.rthread:
current = current.right
else:
current = current.right
while not current.lthread:
current = current.left
时间复杂度O(n),空间复杂度O(1)。
〔4. 线索二叉树的应用场景〕
- 内存受限环境:如嵌入式设备中无法使用栈
- 频繁遍历场景:避免重复计算前驱/后继
- 并行算法:线索化后可并行遍历子树
现代数据库系统(如SQLite)在B+树节点中也采用类似思路存储前驱指针,加速范围查询。
⛰️堆结构与二叉树
堆(Heap)是基于完全二叉树实现的优先队列,满足:
- 最大堆:父节点值 ≥ 子节点值
- 最小堆:父节点值 ≤ 子节点值
〔1. 堆的数组实现〕
完全二叉树可用数组紧凑存储:
class MinHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
〔2. 堆操作实现〕
上滤(插入):
def heap_insert(heap, val):
heap.append(val)
i = len(heap) - 1
while i > 0 and heap[parent(i)] > heap[i]:
heap[i], heap[parent(i)] = heap[parent(i)], heap[i]
i = parent(i)
下滤(删除):
def heapify(heap, i):
smallest = i
left = left_child(i)
right = right_child(i)
if left < len(heap) and heap[left] < heap[smallest]:
smallest = left
if right < len(heap) and heap[right] < heap[smallest]:
smallest = right
if smallest != i:
heap[i], heap[smallest] = heap[smallest], heap[i]
heapify(heap, smallest)
〔3. 堆的应用〕
- Top K问题:维护大小为k的最小堆
- 合并K个有序链表:用堆选择最小节点
- 堆排序:建堆O(n),排序O(n log n)
〔4. Python内置堆〕
Python的heapq模块实现最小堆:
import heapq
# 建堆
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)
# 插入
heapq.heappush(heap, 9)
# 删除最小值
min_val = heapq.heappop(heap)
注意:heapq仅支持最小堆,最大堆可通过取反实现。
💻二叉树应用场景
〔1. 表达式树〕
表达式树是二叉树的典型应用,叶节点为操作数,内部节点为操作符:
+
/ \
* 5
/ \
3 2
对应表达式:(3 * 2) + 5 = 11
计算表达式值可用后序遍历:
def eval_expr_tree(root):
if not root.left and not root.right:
return root.val
left_val = eval_expr_tree(root.left)
right_val = eval_expr_tree(root.right)
if root.val == '+':
return left_val + right_val
elif root.val == '-':
return left_val - right_val
elif root.val == '*':
return left_val * right_val
else:
return left_val / right_val
〔2. 字典树(Trie)〕
字典树是多叉树,常用于字符串查找:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
虽然非二叉树,但其递归结构与二叉树思想一致。
〔3. 决策树〕
机器学习中决策树用于分类,每个节点为特征判断:
- 根节点:最有效特征
- 内部节点:次级特征
- 叶节点:分类结果
决策树的构建涉及信息增益、基尼指数等计算,与二叉树遍历密切相关。
〔4. 文件系统树〕
操作系统文件系统采用树形结构组织目录:
/
├── home/
│ ├── user/
│ │ ├── documents/
│ │ └── downloads/
│ └── admin/
└── var/
└── log/
遍历目录树是二叉树应用的扩展,支持递归查找、文件统计等操作。
〔5. 网页DOM树〕
HTML文档的DOM结构是树形结构:
<html>
<head>...</head>
<body>
<div>
<p>Hello</p>
</div>
</body>
</html>
JavaScript操作DOM树时,常使用递归遍历节点。
📚LeetCode高频题解
〔1. 二叉树最大深度(104)〕
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
递归求解,时间复杂度O(n),空间复杂度O(h)。
〔2. 对称二叉树(101)〕
def is_symmetric(root):
def is_mirror(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val and
is_mirror(t1.left, t2.right) and
is_mirror(t1.right, t2.left))
return is_mirror(root, root)
关键:比较左右子树是否镜像对称。
〔3. 路径总和(112)〕
def has_path_sum(root, target_sum):
if not root:
return False
if not root.left and not root.right:
return root.val == target_sum
return (has_path_sum(root.left, target_sum - root.val) or
has_path_sum(root.right, target_sum - root.val))
前序遍历中累加路径值,叶节点判断是否满足条件。
〔4. 二叉树的最大路径和(124)〕
路径可任意起点终点,但不能分叉:
def max_path_sum(root):
max_sum = float('-inf')
def dfs(node):
nonlocal max_sum
if not node:
return 0
left_gain = max(dfs(node.left), 0)
right_gain = max(dfs(node.right), 0)
# 当前节点作为最高点的路径和
current_path = node.val + left_gain + right_gain
max_sum = max(max_sum, current_path)
# 返回单侧最大路径
return node.val + max(left_gain, right_gain)
dfs(root)
return max_sum
该题考察全局最优解与局部最优解的权衡。
〔5. 二叉搜索树中第K小的元素(230)〕
def kth_smallest(root, k):
stack = []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.right
利用BST中序遍历有序的性质。