Leetcode只二叉树中序遍历（python解法）

张开发
• 2026/4/9 1:22:26 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

Leetcode只二叉树中序遍历（python解法）
1.题目描述示例 1输入root [1,null,2,3]输出[1,3,2]示例 2输入root []输出[]示例 3输入root [1]输出[1]2.解决方法:中序遍历就是先遍历左子树然后遍历右子树可以使用栈将左子树所有的根节点的val记录下来然后在从底部网上遍历这才是正确的书顺序此时就可以加上左树和根此时遍历右子树即可栈方法# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:result [] # 存放最终遍历结果stack [] # 显式栈模拟递归调用栈current root # 当前正在处理的节点从根开始# 只要栈不为空或者当前节点不为空就继续循环while stack or current:# 一路向左把路径上所有节点压入栈while current:stack.append(current)current current.left# 此时 current 为 None说明已到达最左叶子的左孩子空# 弹出栈顶 —— 这就是当前子树中“最左但未访问”的节点即该子树的根current stack.pop()result.append(current.val) # 访问它加入结果# 转向它的右子树可能为空也可能有内容current current.rightreturn result递归方法def inorderTraversal(root):if not root: # 基础情况return []left_list inorderTraversal(root.left) # 递归处理左子树right_list inorderTraversal(root.right) # 递归处理右子树return left_list [root.val] right_list

更多文章