C++의 반전된 하위 트리

소스와 타겟이라는 두 개의 이진 트리가 있다고 가정합니다. 대상의 하위 트리가 되도록 소스의 반전 T가 있는지 확인해야 합니다. 따라서 T의 모든 자손을 포함하여 값과 구조가 동일한 대상에 노드가 있음을 의미합니다.

우리가 알고 있듯이 다음 중 하나인 경우 트리는 다른 트리의 반전이라고 합니다.

두 나무 모두 비어 있습니다.
왼쪽과 오른쪽 자식은 선택적으로 교환되며 왼쪽 및 오른쪽 하위 트리는 반전됩니다.

따라서 입력이 소스와 같은 경우

C++의 반전된 하위 트리

대상

C++의 반전된 하위 트리

그러면 출력은 True

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

check() 함수를 정의하면 node1, node2,
가 필요합니다.
node1과 node2가 모두 null이면 -
- true를 반환
node1 또는 node2 중 하나가 null이면 -
- 거짓을 반환
node1의 val이 node2의 val과 같지 않으면 -
- 거짓을 반환
op1 :=check(node1의 왼쪽, node2의 왼쪽) and check(node1의 오른쪽, node2의 오른쪽)
op2 :=check(node1의 오른쪽, node2의 왼쪽) and check(node1의 왼쪽, node2의 오른쪽)
op1과 op2 중 적어도 하나가 true일 때 true를 반환합니다.
solve() 함수를 정의하면 소스, 타겟,
소스와 대상이 비어 있으면 -
- true를 반환
소스 또는 대상 중 하나가 null이면 -
- 거짓을 반환
op1 :=검사(대상, 소스)
op1이 참이면 -
- true를 반환
solve(source, left of target) 또는 solve(source, right of target) 중 하나 이상이 true인 경우 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:
   bool check(TreeNode* node1, TreeNode* node2){
      if(!node1 && !node2)
      return true;
      if(!node1 || !node2)
      return false;
      if(node1->val != node2->val) {
         return false;
      }
      bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
      bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
      return op1 || op2;
   }
   bool solve(TreeNode* source, TreeNode* target) {
      if(!target && !source)
         return true;
      if(!target || !source)
         return false;
      bool op1 = check(target, source);
      if(op1)
         return true;
      return solve(source, target->left) || solve(source, target->right);
   }
};
main(){
   Solution ob;
   TreeNode *target = new TreeNode(6);
   target->left = new TreeNode(3);
   target->right = new TreeNode(1);
   target->right->left = new TreeNode(3);
   target->right->right = new TreeNode(2);
   target->right->right->left = new TreeNode(4);
   TreeNode *source = new TreeNode(1);
   source->left = new TreeNode(2);
   source->right = new TreeNode(3);
   source->left->right = new TreeNode(4);
   cout << (ob.solve(source, target));
}

입력

TreeNode *target = new TreeNode(6);
target->left = new TreeNode(3);
target->right = new TreeNode(1);
target->right->left = new TreeNode(3);
target->right->right = new TreeNode(2);
target->right->right->left = new TreeNode(4);
TreeNode *source = new TreeNode(1);
source->left = new TreeNode(2);
source->right = new TreeNode(3);
source->left->right = new TreeNode(4);