二叉樹 - 計數不同節點

如果詢問有關二叉樹中節點數的問題，它會非常容易，但要求我計算二叉樹中不同節點的數目，如下所示。有兩個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

二叉樹 - 計數不同節點

回答

相關問題