二叉树的中序遍历python
时间: 2023-12-13 21:34:08 浏览: 32
以下是Python实现二叉树中序遍历的代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
```
其中,`TreeNode`类表示二叉树的节点,`Solution`类中的`inorderTraversal`方法实现了二叉树的中序遍历,`helper`方法是递归实现的,先遍历左子树,再将根节点加入结果列表,最后遍历右子树。
相关问题
二叉树中序遍历代码python
当然,下面是一个用Python实现的二叉树中序遍历的代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
```
这段代码使用了迭代的方式实现了二叉树的中序遍历。首先定义了一个辅助函数`inorderTraversal`,它接受一个二叉树的根节点作为参数,并返回中序遍历的结果。
在函数内部,我们使用一个栈来辅助遍历。首先将根节点入栈,然后进入一个循环,循环条件是当前节点不为空或者栈不为空。在循环中,首先将当前节点的左子节点依次入栈,直到左子节点为空。然后从栈中弹出一个节点,将其值加入结果列表,并将当前节点指向该节点的右子节点。重复以上步骤,直到遍历完整个二叉树。
最后,返回结果列表即可。
二叉树 中序遍历 结构
二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历一棵二叉树。具体的遍历过程如下:
1. 访问该二叉树的根节点。
2. 遍历根节点的左子树,即对根节点的左子树进行中序遍历。
3. 访问根节点。
4. 遍历根节点的右子树,即对根节点的右子树进行中序遍历。
下面是一个示例代码,实现了二叉树的中序遍历:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
```