c++ - 显示属于树的深度路径的二叉搜索树的节点

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;}

};

这里是 Tree 类的相关部分:

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 的节点才会添加到 vector 中。

我还没有测试过它，但它应该可以工作。您还可以将其创建为一个私有(private)函数，然后创建一个只有节点值的公共(public)函数。

注意:这具有 O(N^2) 的复杂性。要在 O(N) 中完成，您可以记住这些值，这样您就不会计算它们 2 次。