สมมติว่าเรามีไบนารีทรีและเป้าหมายจำนวนเต็ม เราต้องลบโหนดปลายสุดทั้งหมดที่มีค่าเป้าหมาย เราต้องจำไว้ว่าเมื่อเราลบโหนดปลายสุดที่มีค่าเป้าหมายหากโหนดหลักกลายเป็นโหนดปลายสุดและมีค่าเป้าหมายก็ควรถูกลบด้วย (เราจำเป็นต้องทำต่อไปจนกว่าเราจะทำไม่ได้) ดังนั้นหากต้นไม้อยู่ด้านล่าง และเป้าหมายคือ 2 ต้นไม้สุดท้ายก็จะเหมือนกับต้นสุดท้าย -
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีการเรียกซ้ำที่เรียกว่า remLeaf() ซึ่งจะทำการรูทและเป้าหมาย
-
ถ้ารูทเป็นโมฆะ ให้คืนค่า null
-
left :=remLeaf(ซ้ายของรูท, เป้าหมาย)
-
right :=remLeaf(ทางขวาของรูท, เป้าหมาย)
-
หากด้านซ้ายเป็นค่าว่างและด้านขวาเป็นค่าว่างและค่าของรูทเหมือนกับเป้าหมาย ให้คืนค่าเป็นค่าว่าง
-
ทางซ้ายของรูท :=left
-
ทางขวาของรูท :=ขวา
-
คืนค่ารูท
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else { q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else { q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } void tree_level_trav(TreeNode*root){ if (root == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr->val == 0 || curr == NULL){ cout << "null" << ", "; } else { cout << curr->val << ", "; } } } cout << "]"<<endl; } class Solution { public: TreeNode* removeLeafNodes(TreeNode* root, int target) { if(!root || root->val == 0) return NULL; TreeNode* left = removeLeafNodes(root->left, target); TreeNode* right = removeLeafNodes(root->right, target); if(!left && !right && root->val == target){ return NULL; } root->left = left; root->right = right; return root; } }; main() { vector<int> v1 = {1,2,3,2,NULL,2,4}; TreeNode *root = make_tree(v1); Solution ob; tree_level_trav(ob.removeLeafNodes(root, 2)); }
อินพุต
[1,2,3,2,null,2,4] 2
ผลลัพธ์
[1, 3, 4, ]