Python3迭代实现二叉树前序遍历，如何避免长尾问题？

本文共计723个文字，预计阅读时间需要3分钟。

Python3中二叉树前序遍历的递归解决方案+二叉树是分层数据结构，其中每个父节点最多有2个子节点。在今天的文章中，我们将讨论一个在大量技术编码面试中出现的重点主题。

Python3中二叉树前序遍历的迭代解决方案

A Binary Tree

二叉树是分层数据结构，其中每个父节点最多有 2 个子节点。在今天的文章中，我们将讨论一个在大量技术编码面试中出现的重要主题。

问题陈述 ： 鉴于 根 二叉树，返回 其节点值的前序遍历 . 提供迭代解决方案而不是递归解决方案。

解决方案：

预购遍历 在二叉树中按以下顺序发生：

• 先访问根
• 遍历左子树
• 遍历右子树

为了用迭代解决方案解决这个问题，我们必须实现 堆 数据结构。这是一种非线性数据结构，其中操作按 LIFO（后进先出）顺序执行。我们回答的方法很简单，如下所示：

• 我们将初始化两个列表IE一个承载输出，另一个充当我们的堆栈数据结构。堆栈将使用二叉树的根值进行初始化。
• 然后，只要堆栈有值，我们就会在堆栈上执行一个 while 循环。