C ++中的二叉树的对角和？

让我们首先定义一个结构，该结构将表示一个包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

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;
}

接下来，agonal_sum（Node * root，int depth，map <int，int>＆diagonalSum）通过引用获取根节点，当前深度和对角线求和图。如果root不为NULL，则将当前的根数据添加到对角线求和图中的当前深度索引中以获取元素的总和，然后在树上执行递归有序遍历，并在每次移至左子节点。

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被发送到对角线_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循环中使用迭代器对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