C++ 中二叉树的对角线和?
c++server side programmingprogramming
考虑在斜率 -1 的线之间穿过的节点。二叉树的对角线和将通过这些参考线之间存在的所有节点数据的总和来计算。
让我们首先定义一个结构，该结构将表示包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，那么它就是根节点，否则就是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
接下来，我们创建 createNode(int data) 函数，该函数接受一个 int 值，并在创建新节点后将其分配给节点的数据成员。该函数返回指向所创建节点的指针。
Node * createNode(int data){
Node * node = new Node;
node->data = data;
return node;
}
接下来，diagonal_sum(Node *root, intdepth, map<int, int> &diagonalSum) 通过引用获取根节点、当前深度和 diagonalSum 映射。如果 root 不为 NULL，那么我们将当前根数据添加到 diagonalSum 映射中的当前深度索引以获取元素的总和。然后，我们对树执行递归中序遍历，并在移动到左子节点时将深度加 1。
void diagonal_sum(Node *root, intdepth, 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 填充了键值对。接下来，我们创建迭代器，用于迭代 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
