สมมติว่าเรามีไบนารีทรี โดยที่ทุกค่าของโหนดเป็น 0 หรือ 1 เราต้องหาต้นไม้เดียวกันโดยที่ทุกทรีย่อยที่ไม่มี 1 ถูกลบไป ดังนั้นถ้าต้นไม้เป็นเหมือน −
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีการแบบเรียกซ้ำ Solvent() ซึ่งจะใช้โหนด วิธีการจะเป็นเช่น −
-
หากโหนดเป็นโมฆะ ให้คืนค่า null
-
โหนดด้านซ้าย :=แก้ (ซ้ายของโหนด)
-
ทางขวาของโหนด :=แก้ (ทางขวาของโหนด)
-
หากด้านซ้ายของโหนดเป็นโมฆะและด้านขวาของโหนดก็เป็นโมฆะด้วย และค่าโหนดเป็น 0 ให้คืนค่าเป็นโมฆะ
-
โหนดกลับ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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,
