试题详情
简答题编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。
  • 设两个结点分别为A和B，根据题目要求分下面情况讨论：
    ⑴若A为根结点，则A为公共祖先；
    ⑵若A->datadata且root->datadata，root为公共祖先；
    ⑶若A->datadata且B->datadata，则到左子树查找；
    ⑷若A->data>root->data且B->data>root->data，则到右子树查找。
    具体算法如下：

  • 关注下方微信公众号，在线模考后查看

热门试题