Вернуть самый дальний лист бинарного дерева поиска

#cpp #алгоритм #бинарное_дерево

Есть дерево BST заданное как 

struct treeNode {
    int info;
    treeNode *left //левый
    treeNode *right; // правый
    treeNode *parent; // предыдущий
};


Нужно запилить метод, который возвращал бы указатель на самый дальний листик этого
дерева(конец самого длинного пути). Если таких несколько, то на любой из них.

Нужно достать именно указатель на листик, потому что от него дальше я пойду назад
до корня зеркально разворачивать дерево относительно этого пути вот так: 

void mirror (treeNode *farthestLeaf) {
    treeNode *tmp = NULL;
    while (farthestLeaf->parent != NULL) {
        tmp = farthestLeaf->parent->left;
        farthestLeaf->parent->left = farthestLeaf->parent->right;
        farthestLeaf->parent->right = tmp;
        farthestLeaf = farthestLeaf->parent;
    }
}


Есть ли у вас какие-нибудь идеи?
    

Ответы

Ответ 1

Как я уже сказал, здесь будет достаточно банальный обход на основе поиска в глубину
— ничего эффективней придумать не получится.

Пример реализации:

const struct treeNode* findDeapest(const struct treeNode* cur, int *deapth) {
  const struct treeNode *rv = cur;
  int curDeapth=*deapth;

  if (cur->left) {
    (*deapth)++;
    rv = findDeapest (cur->left, deapth);
  }
  if (cur->right) {
    int rightDeapth=curDeapth+1;
    const struct treeNode *rightDeapest = findDeapest (cur->right, &rightDeapth);
    if (rightDeapth>*deapth) {
      *deapth = rightDeapth;
      rv = rightDeapest;
    }
  }
  return rv;
}

//вызов
int deapth = 0;
struct treeNode* deapest = findDeapest (myTreeRooteNode, &deapth);