arrays - 如何识别二叉搜索树的叶节点

Question

我最近遇到了以下据说在技术面试中被问到的问题:

Given the preorder traversal of a binary search tree, how do we identify the leaf nodes without building the tree?

例如:[5,3,2,4,8,7,9]

无论是谁发帖，问题都含糊不清，鉴于含糊不清，我不太确定这个问题应该采用什么方法，而且我无法在网上找到经过验证的解决方案。

这个问题应该怎么解决？

Answer 1

考虑您的示例:[5,3,2,4,8,7,9]

取第一个元素:5。

因为这是一个前序遍历，那肯定是根节点。

现在，在前序遍历中，在根 u 之后，left subtree 和 right subtree 递归。

而且你还知道在 BST 中:

 nodes in left subtree < root < nodes in right subtree 

因此在 5 之后，系列中所有小于 5 的元素都属于左子树。右也类似。

所以你最终得到了这个(你不需要明确地创建树):

        5
     /    \
  [3,2,4] [8,7,9]

现在 [3,2,4] 是左子树部分的前序遍历，[8,7,9] 是右子树部分。

对两个子数组进行递归，当你剩下的数组大小为 1 时，这就是叶子。