C++で特定の二分木を剪定するプログラム

すべてのノードの値が0または1のいずれかであるバイナリツリーがあるとします。1を含まないすべてのサブツリーが削除された同じツリーを見つける必要があります。したがって、ツリーが次のような場合-

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

• 再帰メソッドsolve（）を定義します。これにより、ノードが取得されます。メソッドは次のようになります-

• ノードがnullの場合、nullを返します

• ノードの左側：=solve（ノードの左側）

• ノードの権利：=solve（ノードの権利）

• ノードの左側がnullで、ノードの右側もnullで、ノード値が0の場合、nullを返します

• リターンノード

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

例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void inorder(TreeNode *root){
   if(root){
      inorder(root->left);
      cout << root->val << ", ";
      inorder(root->right);
   }
}
class Solution {
   public:
   TreeNode* pruneTree(TreeNode* node) {
      if(!node)return NULL;
      node->left = pruneTree(node->left);
      node->right = pruneTree(node->right);
      if(!node->left && !node->right && !node->val){
         return NULL;
      }
      return node;
   }
};
main(){
   TreeNode *root = new TreeNode(1);
   root->left = new TreeNode(1);
   root->right = new TreeNode(0);
   root->left->left = new TreeNode(1);
   root->left->right = new TreeNode(1);
   root->right->left = new TreeNode(0);
   root->right->right = new TreeNode(1);
   root->left->left->left = new TreeNode(0);
   Solution ob;
   inorder(ob.pruneTree(root));
}

入力

TreeNode *root = new TreeNode(1);
root−>left = new TreeNode(1);
root−>right = new TreeNode(0);
root−>left−>left = new TreeNode(1);
root−>left−>right = new TreeNode(1);
root−>right−>left = new TreeNode(0);
root−>right−>right = new TreeNode(1);
root−>left−>left−>left = new TreeNode(0);

出力

1, 1, 1, 1, 0, 1,