首页二叉树中序遍历输出序列

二叉树中序遍历输出序列

时间: 2025-01-23 21:02:35 浏览: 36

### 二叉树中序遍历输出序列 #### Python 实现方式对于给定的 `root` 节点，可以采用递归的方式实现二叉树的中序遍历。此过程遵循访问左子树、根节点以及右子树的原则。 ```python def inorderTraversal(root): result = [] def traverse(node): if node is None: return traverse(node.left) # 左 result.append(node.val) # 中 traverse(node.right) # 右 traverse(root) return result ``` 另一种非递归的方法利用栈来模拟递归调用的过程[^2]： ```python def inorderTraversal(root): stack, output = [], [] current = root while True: if current is not None: stack.append(current) current = current.left # 移动到最左边 elif(stack): current = stack.pop() output.append(current.val) # 访问中间结点 current = current.right # 进入右边分支 else: break return output ``` 这两种方法都能有效地完成二叉树的中序遍历并返回相应的数值列表[^1]。

阅读全文