这是我对包含 childrenSum 方法的二叉树的实现。
struct BTree
{
struct NodeTree
{
NodeTree (int in) : data(in) { left = nullptr; right = nullptr;}
NodeTree* left;
NodeTree* right;
int data;
};
NodeTree* head;
BTree(std::initializer_list<int> inList)
{
head = nullptr;
for (auto elem : inList)
{
NodeTree* nodeTree = new NodeTree(elem);
insert(nodeTree);
}
}
void insert( NodeTree* newElem )
{
if (head == nullptr)
{
head = newElem;
return;
}
insert2End(head, newElem);
}
void insert2End( NodeTree* current, NodeTree* newElem )
{
std::deque<NodeTree*> queue;
queue.push_back(current);
NodeTree* lastElem = nullptr;
while (!queue.empty())
{
lastElem = queue.front();
queue.pop_front();
if (lastElem->left)
queue.push_back(lastElem->left);
else
{
lastElem->left = newElem;
break;
}
if (lastElem->right)
queue.push_back(lastElem->right);
else
{
lastElem->right = newElem;
break;
}
}
}
int postOrderTreeTraverser(NodeTree* in)
{
int totalSum = 0;
if (in->left)
totalSum += postOrderTreeTraverser(in->left);
if (in->right)
totalSum += postOrderTreeTraverser(in->right);
int returnVal = in->data;
if (in->left != nullptr || in->right != nullptr )
in->data = totalSum;
return returnVal;
}
void childrenSum()
{
if (head == nullptr)
{
return;
}
postOrderTreeTraverser(head);
}
};