核心内容摘要
解码未来之境：18-xxxxxl19d18与18-19d-18的终极博弈，谁才是性能之巅？
给定一个二叉树的根节点root返回它的中序遍历。
示例 1输入root [1,null,2,3]输出[1,3,2]示例 2输入root []输出[]示例 3输入root [1]输出[1]提示树中节点数目在范围[0, 100]内-100 Node.val 100递归解法利用递归的 “左→根→右” 顺序遍历是中序遍历的直观实现。
Python代码from typing import Optional, List class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] # 递归辅助函数实现中序遍历「左→根→右」的核心逻辑 def traverse(node: Optional[TreeNode]): if node: # 节点非空时才遍历递归终止条件node is None traverse(node.left) # 第一步遍历左子树 result.append(node.val) # 第二步访问当前根节点 traverse(node.right) # 第三步遍历右子树 traverse(root) # 从根节点开始递归遍历 return result if __name__ __main__: # 实例化解题类 sol Solution() # 示例1构建树 [1,null,2,3] → 输出 [1,3,2] root1 TreeNode(
root
right TreeNode(
root
right.left TreeNode(
print(示例1输出, sol.inorderTraversal(root
) print(预期结果, [1, 3, 2]) print(- *
# 示例2构建空树 [] → 输出 [] root2 None print(示例2输出, sol.inorderTraversal(root
) print(预期结果, []) print(- *
# 示例3构建树 [1] → 输出 [1] root3 TreeNode(
print(示例3输出, sol.inorderTraversal(root
) print(预期结果, [1])LeetCode提交代码# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) - List[int]: result [] # 递归辅助函数实现“左→根→右”的遍历逻辑 def traverse(node: Optional[TreeNode]): if node: traverse(node.left) # 先遍历左子树 result.append(node.val) # 再访问当前根节点 traverse(node.right) # 最后遍历右子树 traverse(root) return result程序运行截图展示
总结本文介绍了二叉树中序遍历的递归实现方法。
中序遍历按照左子树→根节点→右子树的顺序访问节点。
通过Python代码演示了递归解法定义了一个辅助函数traverse来实现这一逻辑先递归遍历左子树然后访问当前节点值最后递归遍历右子树。
提供了三个测试用例验证正确性包含单节点树、空树和典型二叉树的情况。
时间复杂度为O(n)空间复杂度为O(n)递归栈空间。
该方法直观体现了中序遍历的定义是解决此类问题的经典递归范式。