C ++の二分木の対角和？

勾配-1の線の間を通過するノードを検討します。二分木の対角線の合計は、これらの参照線の間に存在するすべてのノードデータの合計によって計算されます。

まず、データとその左右のノードの子を含むツリーノードを表す構造体を定義しましょう。これが最初に作成されるノードの場合はルートノード、それ以外の場合は子ノードです。

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

次に、int値を取得するcreateNode（int data）関数を作成し、新しいノードを作成した後、それをノードのデータメンバーに割り当てます。この関数は、作成されたノードへのポインタを返します。

Node * createNode(int data){
   Node * node = new Node;
   node->data = data;
   return node;
}

次に、diagonal_sum（Node * root、intdepth、map ＆diagonalSum）は、ルートノード、現在の深度、およびdiagonalSumマップを参照して取得します。ルートが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);
   }
}

main関数内で、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ループ内でイテレータを使用して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