C++で二分木の右葉の合計を見つけるプログラム

二分木があるとすると、与えられた二分木のすべての正しい葉の合計を見つける必要があります。

したがって、入力が次のような場合

バイナリツリーにはそれぞれ値7と10の2つの右葉があるため、出力は17になります。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これにより、ノード、追加、

  が取得されます。

• ノードがnullの場合、-

  • 戻る

• ノードの左側がnullで、ノードの右側がnullで、addがゼロ以外の場合、-

  • ret：=ret+ノードの値

• dfs（ノードの左側、false）

• dfs（ノードの右側、true）

• メインの方法から、次のようにします-

• ret：=0

• dfs（root、true）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   int ret = 0;
   void dfs(TreeNode* node, bool add){
      if(!node)
      return ;
      if(!node−>left && !node->right && add){
         ret += node−>val;
      }
      dfs(node−>left, false);
      dfs(node−>right, true);
   }
   int solve(TreeNode* root) {
      ret = 0;
      dfs(root, true);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(3);
   root−>left = new TreeNode(9);
   root−>right = new TreeNode(10);
   root−>left−>left = new TreeNode(15);
   root−>left−>right = new TreeNode(7);
   cout << (ob.solve(root));
}

入力

TreeNode *root = new TreeNode(3);
root−>left = new TreeNode(9);
root−>right = new TreeNode(10);
root−>left−>left = new TreeNode(15);
root−>left−>right = new TreeNode(7);

出力

17