分析代码:class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def build_tree(postorder): if not postorder: return None root = TreeNode(postorder[-1]) i = 0 while i < len(postorder) - 1 and postorder[i] < root.val: i += 1 root.left = build_tree(postorder[:i]) root.right = build_tree(postorder[i:-1]) return root def preorder_traversal(root): if not root: return [] stack, res = [root], [] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res # 测试代码 postorder = [1, 3, 2, 5, 7, 6, 4] root = build_tree(postorder) print(preorder_traversal(root))
时间: 2024-03-07 07:51:22 浏览: 68
这段 Python 代码实现了根据二叉搜索树的后序遍历序列构建二叉搜索树,并输出其先序遍历序列。以下是代码的分析:
1. 定义了一个 `TreeNode` 类,表示二叉树的节点,包含一个值属性 `val` 和两个指针属性 `left` 和 `right`,分别指向左子树和右子树。
2. `build_tree` 函数用于根据输入的后序遍历序列 `postorder` 构建二叉搜索树,返回根节点。如果 `postorder` 为空,则返回 `None`。
3. 在 `build_tree` 函数中,首先根据 `postorder` 的最后一个元素创建根节点 `root`。然后找到第一个大于等于根节点值的元素的下标 `i`,将 `postorder` 分为左右两个部分,左部分为该节点的左子树的后序遍历序列,右部分为该节点的右子树的后序遍历序列。递归调用 `build_tree` 函数构建左子树和右子树,并将它们分别设为 `root` 的左孩子和右孩子。
4. `preorder_traversal` 函数用于输出二叉搜索树的先序遍历序列。如果输入的根节点 `root` 为空,则返回一个空列表。
5. 在 `preorder_traversal` 函数中,使用栈来实现先序遍历,将根节点压入栈中,并在每次出栈时将当前节点的值加入结果列表 `res` 中。同时,依次将当前节点的右孩子和左孩子压入栈中,保证先遍历左子树,再遍历右子树。
6. 最后,通过输入一个后序遍历序列 `postorder`,调用 `build_tree` 函数构建二叉搜索树,并将根节点传入 `preorder_traversal` 函数,输出先序遍历序列。
综上所述,这段 Python 代码实现了根据二叉搜索树的后序遍历序列构建二叉搜索树,并输出其先序遍历序列的功能。
阅读全文