모든 노드의 값이 0 또는 1인 이진 트리가 있다고 가정합니다. 1을 포함하지 않는 모든 하위 트리가 삭제된 동일한 트리를 찾아야 합니다. 트리가 다음과 같다면 -
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
재귀 메서드 solve()를 정의하면 노드가 사용됩니다. 방법은 다음과 같습니다 -
-
노드가 null이면 null을 반환합니다.
-
노드 왼쪽 :=해결(노드 왼쪽)
-
노드 오른쪽 :=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,