Отображение узлов двоичного дерева поиска, которое принадлежит пути глубины дерева

Question

У меня есть метод в классе Tree, который вычисляет глубину двоичного дерева поиска.

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

Например, рассмотрим следующее дерево:

 10 
    /\ 
    6 13 
/\  \  
    4 9  14 
//
3 8 

Мне нужно производить узлы: 8,9,6,10

У меня есть этот Node класс:

class Node { 

private: 
    Node *left; 
    Node *right; 
    int value; 
public: 
    Node(int v = 0) : left(NULL) , right(NULL) , value(v) { cout << "Node construcotr  " << endl;} 

    Node *getLeft() {return this->left;} 
    void setLeft(Node *n) {this->left = n;} 
    Node *getRight() {return this->right;} 
    void setRight(Node *n) {this->right = n;} 
    int getVal() {return this->value;} 

}; 

И вот соответствующая часть класса :

class Tree { 

private: 
    Node* root; 
    vector<int> vec; /*.....*/ 

int calcDepth(Node *n) 
{ 
if (n == NULL) 
    return 0; 
else 
{ 
    int ld = calcDepth(n->getLeft()); 
    int rd = calcDepth(n->getRight()); 

    if (ld > rd) 
    { 
     if (n->getLeft() != NULL) vec.push_back(n->getLeft()->getVal()); 
     return ld + 1; 
    } 
    else 
    { 
     if (n->getRight() != NULL) vec.push_back(n->getRight()->getVal()); 
     return rd + 1; 
    } 
} 
} // end of calcDepth 

На данный момент это дает мне частичное решение (исключая корень и учитывая узел, который не является частью этого пути).

Может кто-нибудь помочь мне исправить этот код?

Кроме того, любые другие комментарии по поводу реализации также будут замечательными.

Answer 1

Вы должны убедиться, что когда он вызывает push_back, это один из узлов в пути. Поскольку ваш текущий алгоритм добавляет узлы для каждого узла.

class Tree { 

private: 
    Node* root; 
    vector<int> vec; /*.....*/ 

int calcDepth(Node *n,int isInPath) 
{ 
if (n == NULL) 
    return 0; 
else 
{ 
    int ld = calcDepth(n->getLeft(),0); 
    int rd = calcDepth(n->getRight(),0); 

     if(isInPath){ 
     vec.push_back(n->getVal()); 
     if (ld > rd) 
     { 
      calcDepth(n->getLeft(),isInPath); 
      return ld + 1; 
     } 
     else 
     { 
      calcDepth(n->getRight(),isInPath); 
      return rd + 1; 
     } 
     } 
    return max(ld+1,rd+1); 
} 

} // end of calcDepth 

Я добавил переменную isInPath, то есть 1, если текущий узел находится в пути, и 0, если это узел. Вы назовете это с помощью корня и 1.

Он находит максимум два, и только затем вызывает с isInPath == 1. И с помощью этого метода только векторы с isInPath == 1 будут добавлены к вектору.

Я не проверял его, но он должен работать. Вы также можете создать это как частную функцию, а затем общедоступную с только значением узла.

Примечание: это сложность O (N^2). Чтобы сделать это в O (N), вы можете запомнить значения, чтобы вы их не вычисляли 2 раза.