添加一段中序遍历二叉树的代码python
时间: 2023-10-12 17:12:22 浏览: 131
当然可以!以下是一个中序遍历二叉树的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: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
```
其中,我们定义了一个`TreeNode`类来表示二叉树的节点,`inorderTraversal`函数接收一个`root`参数表示二叉树的根节点,返回一个列表,表示中序遍历的结果。函数中使用了一个栈`stack`来辅助遍历,`cur`表示当前遍历的节点。具体的遍历过程如下:
1. 如果当前节点`cur`不为空,将其入栈,并将其指向其左子节点`cur.left`;
2. 如果当前节点`cur`为空,说明已经遍历到最左边的节点,将栈顶元素弹出,并将其值加入结果列表`res`,然后将当前节点`cur`指向其右子节点`cur.right`;
3. 重复步骤1和2,直到栈为空且当前节点`cur`为空。
这样就完成了中序遍历二叉树的操作,得到了节点值的列表`res`。
阅读全文