B2.4.4–5 · HL 递归
二叉树遍历 · HL 应用
Python · 逐步执行
二叉树遍历 · HL 应用
中序遍历依次访问左子树、当前节点和右子树。
Python 实现
1visits = []23def tree_traversal(node):4 if node is None:5 return6 tree_traversal(node["left"])7 visits.append(node["value"])8 tree_traversal(node["right"])B2.4.4 应用，不属于 B2.4.5 对分支代码的要求。每个字典代表一个节点；None 表示没有子节点。此树是二叉搜索树，因此中序遍历输出有序结果。每个节点仅访问一次：时间复杂度为 O(n)，辅助栈空间为 O(h)，其中 h 为树高，不计输出日志。