이진 트리와 정수 대상이 있다고 가정하고 값 대상이 있는 모든 리프 노드를 삭제해야 합니다. 부모 노드가 리프 노드가 되고 값 대상이 있는 경우 값 대상이 있는 리프 노드를 삭제하면 해당 노드도 삭제되어야 함을 명심해야 합니다(할 수 없을 때까지 계속해야 함). 따라서 트리가 아래와 같고 대상이 2이면 최종 트리는 마지막 트리와 같습니다. -
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
remLeaf()라는 재귀 메서드를 정의하면 루트와 대상이 사용됩니다.
-
루트가 null이면 null을 반환
-
왼쪽 :=remLeaf(루트의 왼쪽, 대상)
-
right :=remLeaf(루트의 오른쪽, 대상)
-
왼쪽이 null이고 오른쪽이 null이고 루트 값이 대상과 같으면 null을 반환합니다.
-
루트의 왼쪽 :=왼쪽
-
루트의 오른쪽 :=오른쪽
-
루트 반환
예시(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, ]