한 도둑이 다시 자신의 도둑을 위한 새로운 장소를 찾았다고 가정해 보겠습니다. 이 지역에는 단 하나의 입구가 있으며 그 입구를 "루트"라고 합니다. 루트 외에 각 집에는 단 하나의 부모 집이 있습니다. 견학 후 똑똑한 도둑은 "이곳의 모든 집이 이진 트리를 형성한다"고 느꼈다. 그리고 같은 날 밤에 직접 연결된 2채의 집이 침입하면 자동으로 경찰에 연락합니다. 도둑이 경찰에 알리지 않고 오늘 밤 도둑질할 수 있는 최대 금액을 찾아야 합니다. 트리가 다음과 같다면 -
그러면 출력은 7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve()라는 메서드를 정의하면 노드가 필요합니다.
-
노드가 null이면 쌍을 반환합니다(-infinity, 0)
-
leftVal :=노드 왼쪽, rightVal :=노드 오른쪽
-
leftVal의 첫 번째 요소:=leftVal의 첫 번째 요소의 최대값 및 0
-
leftVal의 두 번째 요소:=leftVal의 두 번째 요소의 최대값 및 0
-
rightVal의 첫 번째 요소:=rightVal의 첫 번째 요소의 최대값 및 0
-
rightVal의 두 번째 요소:=rightVal의 두 번째 요소의 최대값 및 0
-
currVal :=노드 값의 최대값과 0
-
cantBeAdded :=currVal + leftVal의 두 번째 값 + rightVal의 두 번째 값
-
canBeAdded :=(leftVal의 첫 번째 값 + rightVal의 첫 번째 값)의 최대값과 (leftVal의 두 번째 값, rightVal의 두 번째 값, leftVal의 두 번째 값 + rightVal의 두 번째 값, leftVal의 두 번째 값 + rightVal의 첫 번째 값)의 최대값, rightVal의 두 번째 값 + leftVal의 첫 번째 값)
-
쌍을 반환(cantBeAdded, canBeAdded)
-
메인 메소드에서 :=solve(root) 를 만들고, a의 첫 번째 값의 max와 두 번째 값의 a를 반환합니다.
예시(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; } const int INF = -1e8; class Solution { public: void printData(pair <int,int> t){ cout << t.first << " " << t.second << endl; } pair <int,int> solve(TreeNode* node){ if(!node){ return {INF,0}; } pair <int,int> leftVal = solve(node->left); pair <int,int> rightVal = solve(node->right); leftVal.first = max(leftVal.first,0); leftVal.second = max(leftVal.second,0); rightVal.second = max(rightVal.second,0); rightVal.first = max(rightVal.first,0); int currentVal = max(node->val,0); int cantBeAdded = currentVal + leftVal.second + rightVal.second; int canBeAdded =max(leftVal.first + rightVal.first,max({ leftVal.second,rightVal.second,leftVal.second + rightVal.second,leftVal.second+rightVal.first,rightVal.second+leftVal.first })); return {cantBeAdded,canBeAdded}; } int rob(TreeNode* root) { pair <int,int> a = solve(root); return max(a.first,a.second); } }; main(){ Solution ob; vector<int> v = {3,2,3,NULL,3,NULL,1}; TreeNode *root = make_tree(v); cout << (ob.rob(root)); }
입력
[3,2,3,null,3,null,1]
출력
7