C++에서 이진 트리의 의사 회문 경로

<시간/>

노드 값이 1에서 9 사이의 숫자인 이진 트리가 있다고 가정합니다. 이진 트리의 한 경로는 경로에 있는 노드 값의 하나 이상의 순열이 회문일 때 의사 회문이라고 합니다. 루트 노드에서 리프 노드로 가는 의사 회문 경로의 수를 찾아야 합니다.

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

루트 노드에서 리프 노드로 가는 세 개의 경로가 있기 때문에 출력은 2가 됩니다. 빨간색 경로는 [2,3,3]을 따르고 녹색 경로는 [2,1,1]을 따르고 경로는 [ 2,3,1]. 빨간색 경로 [2,3,3]을 [3,2,3]으로 재배열할 수 있고 녹색 경로 [2,1,1]을 재배열할 수 있으므로 이러한 경로 중 빨간색 경로와 녹색 경로만 의사 회문 경로입니다. [1,2,1]로.

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

ok() 함수를 정의하면 배열 v가 필요합니다.
홀수 :=0
각 요소에 대해 v −
- 홀수 :=홀수 + 그것 AND 1
홀수가 0이거나 홀수가 1이면 true를 반환하고 그렇지 않으면 false를 반환합니다.
dfs() 함수를 정의하면 노드, 배열 v,
가 사용됩니다.
노드가 null이면 -
- 반환
v[노드의 값]을 1 증가
노드의 왼쪽이 null이고 노드의 오른쪽이 null인 경우 -
- ok(v)가 참이면 -
  - (ret 1 증가)
- v[노드의 값]을 1 감소
- 반환
dfs(노드 왼쪽, v)
dfs(노드의 오른쪽, v)
v[노드의 값]을 1 감소
기본 방법에서 다음을 수행하십시오 -
ret :=0
크기가 10인 배열 cnt 정의
dfs(루트, cnt)
리턴 렛

예시

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

#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 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;
}
class Solution {
public:
   int ret;
   bool ok(vector <int>& v){
      int odd = 0;
      for (auto& it : v) {
         odd += it & 1;
      }
      return odd == 0 || odd == 1;
   }
   void dfs(TreeNode* node, vector <int>& v){
      if (!node)
         return;
      v[node->val]++;
      if (!node->left && !node->right) {
         if (ok(v))
            ret++;
         v[node->val]--;
         return;
      }
      dfs(node->left, v);
      dfs(node->right, v);
      v[node->val]--;
   }
   int pseudoPalindromicPaths (TreeNode* root) {
      ret = 0;
      vector<int> cnt(10);
      dfs(root, cnt);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,3,1,3,1,NULL,1};
   TreeNode *root = make_tree(v);
   cout << (ob.pseudoPalindromicPaths(root));
}

입력

{2,3,1,3,1,NULL,1}