使用 Python 从二叉搜索树的前序遍历中获取叶节点

什么是二叉搜索树？

二叉树是一种二元数据结构，包含不同的节点，其中每个节点最多有两个子节点。这些节点遵循一些属性，包括

• 二叉树的左子节点值小于根节点的值。
• 二叉树的右子节点值大于根节点的值。
• 所有子节点都必须遵循上述属性。

我们可以通过不同的方式遍历二叉搜索树：

1. 中序
2. 前序
3. 后序

中序遍历算法

• 左子树
• 根节点
• 右子树

前序遍历算法

• 根节点
• 左子树
• 右子树

后序遍历算法

• 左子树
• 右子树
• 根节点

问题陈述

我们有一个二叉搜索树的前序遍历。我们需要从给定的二叉搜索树前序遍历中打印叶子节点。二叉搜索树可以有任意数量的叶子节点。

假设所有节点值都是正数，并且已经按前序排列。我们需要从树中打印叶子节点。

让我们通过几个例子来理解这个问题。

示例 1

输入

输出

70 149 388

说明

给定的二叉搜索树是

第一个元素将是根节点，因为在前序遍历中，我们首先遍历根节点，然后是左子树，最后是右子树。大于根节点的元素是左子树中的元素，其余的在右子树中。使用此输入构建二叉搜索树后，我们得到叶子节点元素为 [70, 149, 388]。

示例 2

输入

{ 42, 30, 27, 23, 19, 22, 26, 29, 15, 32, 31, 35, 38 }

输出

15 22 26 29 31 38

说明

第一个元素将是根节点，因为在前序遍历中，我们首先遍历根节点，然后是左子树，最后是右子树。使用此输入构建二叉搜索树后，我们得到叶子节点为元素 [15, 22, 26, 29, 31, 38]。

有两种方法可以从二叉搜索树的前序遍历中找到叶子节点。

1. 简单方法

在这个方法中，我们将首先使用中序和前序数组来找出二叉搜索树的前序遍历。我们首先遍历前序数组，然后在中序数组中找到元素。

代码

输出

The Leaf Nodes present in the binary search tree are: 
15 22 26 29 31 38 

说明

首先，我们将遍历数组以在中序数组中找到元素。我们使用了二分查找，因为它会以升序给出遍历结果。我们已经为查找元素设置了范围 [L, R]。如果 L 的值等于 R，我们就找到了叶子节点。现在，我们将从前序数组的根节点的L = 0 和 R = 节点数 - 1 开始。要搜索左子树的元素，我们将L = 0 和 R = 根节点索引。对于右子树，我们设置 L = 根节点索引 + 1 和 R = 节点数 - 1。

2. 使用栈

我们将使用一个栈并通过两个指针遍历数组。

代码

输出

The Leaf Nodes present in the binary search tree are: 
54 78 44

说明

在这个方法中，我们使用了两个指针，i 和 j。开始时，i = 0 且 j = 1。比较 array[i] 和 array[j]，如果 array[i] > array[j]，这意味着 array[j] 在 a[i] 的左侧。然后，a[i] 将被压入栈。我们将弹出元素直到 array[i] > 栈顶元素，然后打印第 j 个值。第 j 个值将是二叉搜索树的叶子节点。