二叉树 - 计数不同节点

如果询问有关二叉树中节点数的问题，它会非常容易，但要求我计算二叉树中不同节点的数目，如下所示。有两个12值！二叉树 - 计数不同节点

二叉树algoritm节点数量是这样的：

struct Node { 
    string data; 
    struct Node *left; 
    struct Node *right; 
}; 

int getNumberOfNodes(Node* node) 
{ 
    if (node != NULL) 
     return getNumberOfNodes(node->left) + 1 + getNumberOfNodes(node->right); 
    else 
     return 0; 
}

但独特的价值观，实在是太辛苦-_-

来源

2016-03-10 funky-nd

您将需要一组记忆它遇到的所有数字。然后统计集合的大小，然后这是树中唯一的总数。 – Elye

如果您不想使用额外的O（n）内存，您可以从BST创建一个“max heap”，然后遍历其节点，并且每当根等于其子节点时总计数减1。 –

你可以改变你的函数将容器保持你已经遇到过的值。在评论std::set中已经提出了最好的容器。

新代码将是：

int getNumberOfNodes(Node* node, std::set<string>& uniqueValues) 
{ 
    if (node != NULL) 
    { 
     int count = 0; 
     if (uniqueValues.find(node->data) == uniqueValues.end()) 
     { 
      count = 1; 
      uniqueValues.insert (node->data); 
     } 

     return getNumberOfNodes(node->left,uniqueValues) + count + getNumberOfNodes(node->right,uniqueValues); 
    } 
    else 
     return 0; 
}

不那么从您的代码不同。
最后uniqueValues.size()将等于返回的int。
在调用函数之前清除uniqueValues。

来源

2016-03-10 06:26:17 Matteo

woowowowo，很好。谢谢。有效。 btw：我纠正了这一行：return getNumberOfNodes（node-> left，uniqueValues）+ count + getNumberOfNodes（node-> right，uniqueValues）; –

我更正了它，在答案中，可能在您复制之后。 – Matteo

二叉树 - 计数不同节点

回答

相关问题