Python 中的二叉树前序遍历
c++server side programmingprogramming更新于 2024/9/1 2:28:00
假设我们有一棵二叉树。我们必须返回该树的前序遍历。因此，如果树像 −
那么前序遍历将是:[3,9,20,15,7]
为了解决这个问题，我们将遵循以下步骤 −
- 创建名为 res 和 st 的空列表。
- node := root
- 当 node 或 st 不为空时
- 当 node 不为空时，则
- 将节点的 val 插入 res，将节点插入 st 并设置节点 := left of节点
- temp := st 的最后一个元素，并删除 st 的最后一个元素
- 如果 temp 的右侧可用，则
- node := temp 的右侧
- 当 node 不为空时，则
- return res
让我们看看下面的实现以便更好地理解 −
示例
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def preorderTraversal(self, root): res = [] st = [] node = root while node or st: while node: if node.data != None: res.append(node.data) st.append(node) node = node.left temp = st[-1] st.pop() if temp.right: node = temp.right return res ob1 = Solution() head = make_tree([3,9,20,None,None,15,7]) print(ob1.preorderTraversal(head))
输入
[3,9,20,null,null,15,7]
输出
[3, 9, 20, 15, 7]
