94.二叉树的中序遍历 python

题目

题目描述

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

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
题解

中序遍历（Inorder Traversal）是二叉树的一种遍历方式，其遍历顺序为：先访问左子树，然后访问根节点，末了访问右子树。对于每个子树来说，也是依照相同的访问顺序。这种遍历方法特殊实用于二叉搜索树（BST），因为在BST中进行中序遍历会按照升序访问节点。
解题思路

为了实现中序遍历，我们可以使用递归或迭代的方法：

• 递归法：这是最直观的方法。我们定义一个辅助函数来进行递归调用，在这个过程中，首先递归访问左子树，然后访问当前节点，末了递归访问右子树。
  
• 迭代法：通过显式地使用栈来模拟递归调用的过程。开始时将所有左侧节点压入栈中，直到遇到没有左孩子的节点为止；然后弹出栈顶元素并访问它，接着转向它的右子树，并重复上述过程。
  

下面分别给出这两种方法的 Python 实当代码：
递归法

1. def inorderTraversal(root: TreeNode) -> list:
2.     result = []
3.    
4.     def traverse(node):
5.         if not node:
6.             return
7.         # 先遍历左子树
8.         traverse(node.left)
9.         # 访问根节点
10.         result.append(node.val)
11.         # 最后遍历右子树
12.         traverse(node.right)
13.    
14.     traverse(root)
15.     return result

复制代码

提交结果

迭代法

1. def inorderTraversal(root: TreeNode) -> list:
2.     stack, result = [], []
3.     current = root
4.    
5.     while current or stack:
6.         # 遍历到最左边的节点，并将其沿途的所有节点压入栈中
7.         while current:
8.             stack.append(current)
9.             current = current.left
10.         
11.         # 弹出栈顶元素并访问它
12.         current = stack.pop()
13.         result.append(current.val)
14.         
15.         # 转向右子树
16.         current = current.right
17.    
18.     return result

复制代码

提交结果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。