题目
给定一个二叉树的根节点 root，返回它的中序遍历。
提示
一句话思路：递归 DFS——先遍历左子树，再访问根节点，最后遍历右子树。
- 中序遍历顺序是「左 -> 根 -> 右」，把访问根节点的代码行挪到左子树递归前就是前序，挪到最后就是后序，三种遍历只差这一行的位置。
- 递归终止条件：节点为空就直接返回（空树/叶子节点的空孩子）。
- 时间 O(n)、空间 O(n)：每个节点访问一次，递归栈深度最坏 O(n)（链状树）。
答案
python
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node: Optional[TreeNode]) -> None:
if node is None: # 空节点，递归终止
return
dfs(node.left) # 左：先遍历左子树
ans.append(node.val) # 根：访问当前节点（这行移到前面是前序，移到后面是后序）
dfs(node.right) # 右：再遍历右子树
ans = [] # 存放遍历结果
dfs(root) # 从根节点开始递归
return ans # 返回中序遍历结果
留言板