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

Question

我最近遇到了一个据说在技术面试中被问过的问题:

给定二叉搜索树的前序遍历,我们如何在不构建树的情况下识别叶节点？

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

任何人发布它并且模糊不清,问题都是模糊的,我不确定这个方法应该是什么,我无法在网上找到经过验证的解决方案.

该问题应如何解决？

Answer 1

考虑你的例子: [5,3,2,4,8,7,9]

拿第一个元素:5.

因为这是一个前序遍历,它确实是根节点.

现在,在前序遍历中,在root之后重复左子树然后右子树.

你也知道在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的数组时,那就是叶子.