数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中二叉树的对角线之和？
考虑穿过斜率为 -1 的直线的节点。二叉树的对角线之和将通过计算这些参考线之间存在的节点数据之和来计算。
首先，让我们定义一个结构体，它将表示一个树节点，其中包含数据及其左右子节点。如果这是第一个创建的节点，则它是根节点，否则是子节点。
struct Node { int data; struct Node *leftChild, *rightChild; };
接下来，我们创建 createNode(int data) 函数，该函数接收一个整数值并将其分配给创建新节点后节点的数据成员。该函数返回指向已创建节点的指针。
Node * createNode(int data){ Node * node = new Node; node->data = data; return node; }
接下来，diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum) 通过引用接收根节点、当前深度和 diagonalSum 映射。如果 root 不为 NULL，则我们将当前根数据添加到 diagonalSum 映射中当前深度索引处，以获得元素的总和。然后，我们在树上执行递归中序遍历，并在每次移动到左子节点时将深度加 1。
void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){ if(root){ diagonalSum[depth]+=root->data; diagonal_sum(root->leftChild, depth+1, diagonalSum); diagonal_sum(root->rightChild, depth, diagonalSum); } }
在我们的主函数内部，我们使用 createNode(data) 方法创建一个树，并创建一个映射 SumMap。根节点、当前深度（为 1）和 sumMap 被发送到 diagonal_sum，其中 sumMap 填充了键值对。接下来，我们创建迭代器 it 用于遍历 sumMap 映射。
int main(){ Node *root = createNode(1); root->rightChild = createNode(3); root->rightChild->leftChild = createNode(4); root->rightChild->leftChild->leftChild = createNode(12); root->rightChild->leftChild->rightChild = createNode(7); root->leftChild = createNode(2); root->leftChild->leftChild = createNode(9); root->leftChild->rightChild = createNode(6); root->leftChild->leftChild->rightChild = createNode(10); root->leftChild->rightChild->leftChild = createNode(11); root->rightChild->rightChild = createNode(5); map<int,int> sumMap; diagonal_sum(root, 1, sumMap); map<int,int>::iterator it;
最后，我们使用 for 循环内部的迭代器 it 遍历 SumMap 并打印对角线之和。
for(it=sumMap.begin(); it!=sumMap.end();++it){ int value = it->second; cout<<value<<"\t"; }
示例
让我们看看以下查找二叉树的对角线之和的实现。
#include<iostream> #include<map> using namespace std; struct Node{ int data; struct Node* leftChild, *rightChild; }; Node * createNode(int data){ Node * node = new Node; node->data = data; return node; } void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){ if(root){ diagonalSum[depth]+=root->data; diagonal_sum(root->leftChild, depth+1, diagonalSum); diagonal_sum(root->rightChild, depth, diagonalSum); } } int main(){ Node *root = createNode(1); root->rightChild = createNode(3); root->rightChild->leftChild = createNode(4); root->rightChild->leftChild->leftChild = createNode(12); root->rightChild->leftChild->rightChild = createNode(7); root->leftChild = createNode(2); root->leftChild->leftChild = createNode(9); root->leftChild->rightChild = createNode(6); root->leftChild->leftChild->rightChild = createNode(10); root->leftChild->rightChild->leftChild = createNode(11); root->rightChild->rightChild = createNode(5); map<int,int> sumMap; diagonal_sum(root, 1, sumMap); map<int,int>::iterator it; for(it=sumMap.begin(); it!=sumMap.end();++it){ int value = it->second; cout<<value<<"\t"; } return 0; }
输出
以上代码将产生以下输出：
91942
更新于: 2021-01-16
99 次查看
广告