[算法导论] 94.二叉树的中序遍历

本文主要是介绍[算法导论] 94.二叉树的中序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0.题目

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

1.递归

🍇递归 一个函数实现递归
class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []if root:res+=(self.inorderTraversal(root.left))  #也可以用res.extendres.append(root.val)res+=(self.inorderTraversal(root.right))return res🍇递归 两个函数实现递归 时空o(n)
class Solution:def inorder(self,root,res):if not root: return []self.inorder(root.left,res)res.append(root.val)self.inorder(root.right,res)return resdef inorderTraversal(self, root: TreeNode) -> List[int]:if not root: return []res = []self.inorder(root,res)return res

2. 迭代

🍇用栈迭代，时间空间复杂度o(n) 空间复杂度取决于栈/递归的深度
class Solution:# 

这篇关于[算法导论] 94.二叉树的中序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---