中序遍历二叉树输出中序遍历序列
时间: 2023-11-26 12:58:02 浏览: 37
好的,这是一道经典的二叉树遍历问题。中序遍历二叉树的过程为:先遍历左子树,再访问根节点,最后遍历右子树。具体实现代码如下:
```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]:
if not root:
return []
res = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
```
其中,我们用栈来辅助遍历二叉树。重点是要注意遍历的顺序:先将左子树全部入栈,然后一次弹出栈顶,访问根节点,再将右子树遍历。
相关问题
数据结构中序遍历二叉树图解
好的,我知道你的问题。
中序遍历是二叉树遍历的一种。它的基本思想是:按照左子树、根结点、右子树的顺序,访问二叉树中的所有节点,得到的序列就是二叉树的中序遍历序列。
下面是对二叉树进行中序遍历的图解:
首先,先访问左子树,一直递归到最左下角的叶子节点。如图中的节点A。
然后,依次访问每个节点的根节点,如图中的节点B。
最后,访问右子树,一直递归到最右下角的叶子节点。如图中的节点C。
按照这个顺序,我们访问完整棵二叉树之后,得到的就是中序遍历序列。
用非递归算法中序遍历二叉树,输出其中序序列
非递归算法中序遍历二叉树需要用到栈,具体步骤如下:
1. 将根节点入栈。
2. 只要栈不为空,执行以下操作:
- 将栈顶节点弹出,访问该节点。
- 如果该节点有右子树,将右子树入栈。
- 如果该节点有左子树,将左子树入栈。
3. 遍历结束。
代码如下:
```python
def inorder_traversal(root):
if not root: # 如果根节点为空,直接返回空列表
return []
stack = [] # 栈
res = [] # 用于存储遍历结果
cur = root # 当前节点
while stack or cur:
if cur: # 如果当前节点不为空,将当前节点入栈,并将当前节点更新为左子节点
stack.append(cur)
cur = cur.left
else: # 如果当前节点为空,弹出栈顶节点,访问该节点,将当前节点更新为右子节点
node = stack.pop()
res.append(node.val)
cur = node.right
return res
```
其中,`root` 表示二叉树的根节点,`val` 表示节点的值。函数返回中序遍历的结果列表。