C++의 균등 트리 파티션

<시간/>

n개의 노드가 있는 이진 트리가 있다고 가정하고 원래 트리에서 정확히 한 모서리를 삭제한 후 값의 합이 동일한 두 개의 트리로 트리를 분할하는 것이 가능한지 확인하는 것입니다.

따라서 입력이 다음과 같으면

C++의 균등 트리 파티션

그러면 출력이 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −
하나의 스택 정의
solve() 함수를 정의하면 노드가 필요합니다.
노드가 null이면 -
- 0 반환
leftSum :=해결(노드 왼쪽)
rightSum :=해결(노드 오른쪽)
curr :=val + leftSum + 노드의 rightSum
st에 curr 삽입
통화 반환
주요 방법에서 다음을 수행하십시오 -
해결(루트)
totalSum :=st의 최상위 요소
st
에서 요소 삭제
동안(st가 비어 있지 않음) -
- x :=st의 최상위 요소
- st
  에서 요소 삭제
- y :=totalSum - x
- x가 y와 같으면 -
  - true를 반환
거짓을 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
public:
   stack <int> st;
   int solve(TreeNode* node){
      if (!node)
         return 0;
      int leftSum = solve(node->left);
      int rightSum = solve(node->right);
      int curr = node->val + leftSum + rightSum;
      st.push(curr);
      return curr;
   }
   bool checkEqualTree(TreeNode* root) {
      solve(root);
      int totalSum = st.top();
      st.pop();
      while (!st.empty()) {
         int x = st.top();
         st.pop();
         int y = totalSum - x;
         if (x == y)
            return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(5);
   root->left = new TreeNode(10);
   root->right = new TreeNode(10);
   root->right->left = new TreeNode(2);
   root->right->right = new TreeNode(3);
   cout<<(ob.checkEqualTree(root));
}

입력

TreeNode *root = new TreeNode(5);
root->left = new TreeNode(10);
root->right = new TreeNode(10);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(3);