交互式Python实验室

Binary Tree Traversal

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

advanced 路径

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

解释

Line 13

Build BST: root=4, left=2, right=6, 2.left=1, 2.right=3.

为什么用这种方法？

This is a valid BST: all left subtree values (1,2,3) < root (4) < right subtree values (6). In-order traversal of any BST always produces sorted ascending output — that's the key property we're demonstrating.

Structured Explanation

Overview

二叉树遍历：前序(根-左-右)、中序(左-根-右)、后序(左-右-根)三种递归方式。

Analogy

就像读家谱——中序给出升序后代，前序先祖先，后序先子孙。

Step-by-step

前序: 处理节点→左→右
中序: 左→处理节点→右
后序: 左→右→处理节点
所有方式均需None检查的基础情况

Visual

4 / \ 2 5 / \ 1 3 中序: 1,2,3,4,5 前序: 4,2,1,3,5 后序: 1,3,2,5,4

Common mistakes

混淆三种遍历顺序
忘记None检查的基础情况

Practice questions

用栈实现迭代中序遍历
比较递归和迭代遍历

Time

O(n)

Space

O(h) h为树高

复杂度

时间

O(n)

空间

O(h) — h = tree height

复杂度概览

O(1)

O(log n)

O(n)时间空间

O(n log n)

O(n²)

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

实现二叉树的中序、前序和后序遍历。

提示

这里递归很自然。中序: 左→节点→右。前序: 节点→左→右。后序: 左→右→节点。

代码工作室

Binary Tree Traversal

Monaco就绪

Python就绪

lesson.pyline 13

Loading editor...

输出控制台

0 lines

暂无输出...

现实世界应用

1

Rendering structural DOM trees

2

Compiling mathematical logic expressions

3

Writing JSON parsers

Comments

Loading comments...