[二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/description/) ## 题目描述 给定一个二叉树的根节点 root，返回它的中序遍历结果。 中序遍历的定义：遍历左子树 → 访问根节点 → 遍历右子树 **示例** ```text 输入：root = [1,null,2,3] 输出：[1,3,2] 1 \ 2 / 3 ``` ```text 1 / \ 2 3 / \ \ 4 5 6 中序遍历顺序：4 → 2 → 5 → 1 → 3 → 6 ``` ```text 输入：root = [] 输出：[] ``` ## 解题思路 核心思想是：先递归地访问左子树，然后访问当前节点，最后递归地访问右子树。 **关注遍历执行的顺序: `左根右`** ```python # 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: values = [] def dfs( root_ ): if not root_: return dfs( root_.left ) values.append( root_.val ) dfs( root_.right ) dfs( root ) return values ``` **时间复杂度: `O(n)`** **空间复杂度: `O(h)`** n = 节点总数 h = 树的高度 ( 最坏情况`O(n)` 最好情况`O(log n)` )