LeetCode 94：二叉树的中序遍历 | 递归与迭代

LeetCode 94二叉树的中序遍历 | 递归与迭代一、题目详解1.1 题目描述LeetCode 94二叉树的中序遍历Binary Tree Inorder Traversal给定一个二叉树的根节点root返回它的中序遍历结果。难度Medium示例 1输入root [1,null,2,3] 输出[1,3,2]示例 2输入root [] 输出[]示例 3输入root [1] 输出[1]1.2 题目分析中序遍历的顺序是左子树 - 根节点 - 右子树对于二叉搜索树BST中序遍历的结果是有序序列这是一个非常重要的性质。二、算法实现2.1 递归实现def inorderTraversal(root): result [] def traverse(node): if not node: return # 先递归遍历左子树 traverse(node.left) # 访问当前节点 result.append(node.val) # 递归遍历右子树 traverse(node.right) traverse(root) return result递归思路解析如果当前节点为空直接返回递归处理左子树深入最左节点访问当前节点将值加入结果列表递归处理右子树2.2 迭代实现中序遍历的迭代实现比前序遍历稍复杂需要先遍历到最左节点def inorderTraversal_iterative(root): result [] stack [] current root while current or stack: # 深入到最左节点 while current: stack.append(current) current current.left # 弹出节点访问它 current stack.pop() result.append(current.val) # 转向右子树 current current.right return result迭代思路解析初始化当前节点为根节点栈为空沿着左子树一直向下将所有节点入栈当当前节点为空时弹出栈顶节点并访问将当前节点设置为弹出节点的右子节点重复步骤2-4直到栈为空且当前节点为空2.3 Morris遍历O(1)空间复杂度def inorderTraversal_morris(root): result [] current root while current: if not current.left: # 没有左子树直接访问 result.append(current.val) current current.right else: # 找到左子树的最右节点 predecessor current.left while predecessor.right and predecessor.right ! current: predecessor predecessor.right if not predecessor.right: # 建立线索 predecessor.right current current current.left else: # 恢复树结构并访问 predecessor.right None result.append(current.val) current current.right return result三、复杂度分析3.1 递归实现时间复杂度O(n)每个节点访问一次空间复杂度O(h)递归调用栈的深度3.2 迭代实现时间复杂度O(n)每个节点入栈出栈一次空间复杂度O(h)栈的最大深度3.3 Morris遍历时间复杂度O(n)空间复杂度O(1)不使用额外空间四、边界情况讨论4.1 空树root None # 输出[]4.2 单节点树root TreeNode(1) # 输出[1]4.3 二叉搜索树BST# 4 # / \ # 2 6 # / \ / \ # 1 3 5 7 # 中序遍历[1, 2, 3, 4, 5, 6, 7] 有序4.4 只有左子树的退化树# 3 # / # 2 # / # 1 # 中序遍历[1, 2, 3]五、BST中的应用5.1 验证BST利用中序遍历得到有序序列的性质验证BSTdef isValidBST(root): prev float(-inf) def inorder(node): nonlocal prev if not node: return True if not inorder(node.left): return False if node.val prev: return False prev node.val return inorder(node.right) return inorder(root)5.2 查找BST中第K小的元素def kthSmallest(root, k): count 0 result None def inorder(node): nonlocal count, result if not node or count k: return inorder(node.left) count 1 if count k: result node.val return inorder(node.right) inorder(root) return result5.3 BST转有序链表def convertBSTtoSortedList(root): prev None head None def inorder(node): nonlocal prev, head if not node: return inorder(node.left) if prev: prev.right node node.left None else: head node prev node inorder(node.right) inorder(root) return head六、总结6.1 核心要点要点说明遍历顺序左 → 根 → 右BST特性中序遍历结果为有序序列递归实现简洁直观迭代实现需要先深入左子树6.2 与其他遍历方式对比遍历方式顺序BST应用前序根→左→右树的序列化中序左→根→右验证BST、查找第K小元素后序左→右→根释放资源、计算子树和6.3 扩展思考如何在O(1)空间复杂度下验证BST中序遍历的迭代实现和前序遍历有什么关键区别除了BST中序遍历还有哪些实际应用参考资料LeetCode 94 题解二叉搜索树性质