C++で特定の二分木の左葉ノードの合計を求めます

ルートノードとその左の子と右の子を持つ二分木があるとしましょう。タスクは、親ノードに残されているツリーのリーフノードの合計を見つけることです。

例

入力-1：

出力：

15

説明： 与えられた入力二分木では、すべての左側の葉ノードの合計は9 + 4 + 2 =15です。したがって、出力は15です。

この問題を解決するためのアプローチ

二分木があり、その親に残されているすべてのリーフノードの合計を見つけることがタスクです。

この問題を解決するための再帰的なアプローチは、ルートノードの左側のノードが空かどうかを確認することです。空の場合は、左側のノードの合計を計算し、右側のノードの再帰的な合計を見つけます。したがって、すべてのノードについて、再帰的にチェックし、その合計を見つけます。

• ルートノードとその左の子、および右の子を入力として持つバイナリツリーを取得します。
• 整数関数leftLeafSum（treenode * root）は、ルートノードを入力として受け取り、その親に残されているすべてのリーフノードの合計を返します。
• ルートノードが空またはNULLの場合は、「ゼロ」を返します。それ以外の場合は、ルートノードの左側のノードを確認します。
• ルートノードの左側のノードに子がない場合は、右側のノードを再帰的にチェックします。
• 左の子と右の子の合計を再帰的に返します。

例

#include<bits/stdc++.h>
using namespace std;
struct treenode {
   int data;
   treenode * left;
   treenode * right;
};
struct treenode * createNode(int d) {
   struct treenode * root = new treenode;
   root -> data = d;
   root -> left = NULL;
   root -> right = NULL;
   return root;
}
int leftLeafSum(treenode * root) {
   if (root == NULL) {
      return 0;
   }
   if (root -> left and!root -> left -> left and!root -> left -> right) {
      return root -> left -> data + leftLeafSum(root -> right);
   }
   return leftLeafSum(root -> left) + leftLeafSum(root -> right);
}
int main() {
   struct treenode * root = NULL;
   root = createNode(4);
   root -> left = createNode(2);
   root -> right = createNode(2);
   root -> left -> right = createNode(7);
   root -> left -> left = createNode(5);
   root -> right -> left = createNode(5);
   root -> right -> right = createNode(7);
   int sum = leftLeafSum(root);
   cout << sum << endl;
   return 0;
}

上記のコードを実行すると、次のように出力が生成されます

出力

10

説明： 左側のノードのリーフノードは5と5であり、これらは親に残されているため、すべてのリーフノードの合計は=10になります。