我最近遇到了以下据说在技术面试中被问到的问题:
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]
无论是谁发帖,问题都含糊不清,鉴于含糊不清,我不太确定这个问题应该采用什么方法,而且我无法在网上找到经过验证的解决方案。
这个问题应该怎么解决?
最佳答案
考虑您的示例:[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 时,这就是叶子。
关于arrays - 如何识别二叉搜索树的叶节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42407162/