LeetCode 94. 二叉树的中序遍历 Python3 实现题目给定一个二叉树的根节点 root返回它的 中序遍历。中序遍历顺序左子树 → 根节点 → 右子树示例输入root [1,null,2,3] 输出[1,3,2]解法一递归思路按照「左 → 根 → 右」的顺序递归访问即可。代码fromtypingimportList,Optional# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node:Optional[TreeNode]):ifnotnode:returndfs(node.left)# 左res.append(node.val)# 根dfs(node.right)# 右dfs(root)returnres复杂度· 时间复杂度O(n)每个节点访问一次。· 空间复杂度O(h)h 为树高递归栈深度。解法二迭代显式栈思路用一个栈模拟递归。不断将当前节点及其左子节点入栈直到最左。弹出栈顶节点访问其值然后转向右子节点。代码fromtypingimportList,OptionalclassSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]stack[]currootwhilecurorstack:# 一路向左入栈whilecur:stack.append(cur)curcur.left# 弹出并访问curstack.pop()res.append(cur.val)# 转向右子树curcur.rightreturnres复杂度· 时间复杂度O(n)· 空间复杂度O(h)解法三Morris 遍历O(1) 空间思路利用叶子节点的空右指针指向中序后继从而避免使用栈。若当前节点无左子节点直接访问转向右子节点。若有左子节点找到左子树的最右节点中序前驱· 若其右指针为空指向当前节点然后当前节点向左。· 若其右指针已指向当前节点说明左子树已遍历完断开指针访问当前节点转向右子节点。代码fromtypingimportList,OptionalclassSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]currootwhilecur:ifnotcur.left:# 无左子树直接访问res.append(cur.val)curcur.rightelse:# 找左子树的最右节点中序前驱precur.leftwhilepre.rightandpre.right!cur:prepre.rightifnotpre.right:# 建立线索pre.rightcur curcur.leftelse:# 断开线索访问当前节点pre.rightNoneres.append(cur.val)curcur.rightreturnres复杂度· 时间复杂度O(n)· 空间复杂度O(1)总结解法 时间复杂度 空间复杂度 特点递归 O(n) O(h) 最简洁易理解迭代 O(n) O(h) 避免递归栈溢出Morris O(n) O(1) 空间最优但会临时修改树结构面试中推荐掌握 递归 和 迭代 两种写法Morris 可作为加分项。示例运行# root [1, null, 2, 3]# 1# \# 2# /# 3solSolution()print(sol.inorderTraversal(root))# [1, 3, 2]
