94.二叉树的中序遍历 python
题目题目描述
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
https://i-blog.csdnimg.cn/direct/64b8d898bb374b6a9d12c1479a979c68.png
输入：root =
输出：
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root =
输出：
提示：
树中节点数目在范围 内
-100 <= Node.val <= 100
题解
中序遍历（Inorder Traversal）是二叉树的一种遍历方式，其遍历顺序为：先访问左子树，然后访问根节点，末了访问右子树。对于每个子树来说，也是依照相同的访问顺序。这种遍历方法特殊实用于二叉搜索树（BST），因为在BST中进行中序遍历会按照升序访问节点。
解题思路
为了实现中序遍历，我们可以使用递归或迭代的方法：
[*]递归法：这是最直观的方法。我们定义一个辅助函数来进行递归调用，在这个过程中，首先递归访问左子树，然后访问当前节点，末了递归访问右子树。
[*]迭代法：通过显式地使用栈来模拟递归调用的过程。开始时将所有左侧节点压入栈中，直到遇到没有左孩子的节点为止；然后弹出栈顶元素并访问它，接着转向它的右子树，并重复上述过程。
下面分别给出这两种方法的 Python 实当代码：
递归法
def inorderTraversal(root: TreeNode) -> list:
result = []
def traverse(node):
if not node:
return
# 先遍历左子树
traverse(node.left)
# 访问根节点
result.append(node.val)
# 最后遍历右子树
traverse(node.right)
traverse(root)
return result
提交结果
https://i-blog.csdnimg.cn/direct/e986bd4904ce47c5af5d3d824051c613.png
迭代法
def inorderTraversal(root: TreeNode) -> list:
stack, result = [], []
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
提交结果
https://i-blog.csdnimg.cn/direct/705d2087e54a4f84b0a56c1adf4d88ac.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]