Pseudo-Palindromic Path in a Binary Tree in C ++

Giả sử chúng ta có một cây nhị phân trong đó các giá trị nút là các chữ số từ 1 đến 9. Một đường dẫn trong cây nhị phân được cho là pseudo-palindromic khi ít nhất một hoán vị của các giá trị nút trong đường dẫn là một palindrome. Chúng ta phải tìm số đường dẫn giả palindromic đi từ nút gốc đến các nút lá.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2, điều này là do có ba con đường đi từ nút gốc đến các nút lá - con đường màu đỏ đi theo [2,3,3], con đường màu xanh lá cây theo sau [2,1,1] và đường dẫn [ 2,3,1]. Trong số những con đường này, chỉ có con đường màu đỏ và con đường màu xanh lá cây là những con đường giả palindromic vì con đường màu đỏ [2,3,3] có thể được sắp xếp lại thành [3,2,3] và con đường màu xanh lá cây [2,1,1] có thể được sắp xếp lại dưới dạng [1,2,1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm ok (), điều này sẽ lấy một mảng v,
lẻ:=0
cho mỗi phần tử nó trong v -
- lẻ:=lẻ + nó VÀ 1
trả về true khi số lẻ là 0 HOẶC số lẻ là 1, ngược lại là false
Xác định một hàm dfs (), điều này sẽ lấy nút, mảng v,
nếu nút là null, thì -
- trở lại
tăng v [val of node] lên 1
nếu bên trái của nút là null và bên phải của nút là null, thì -
- nếu ok (v) là đúng, thì -
  - (tăng ret lên 1)
- giảm v [val of node] đi 1
- trở lại
dfs (bên trái của nút, v)
dfs (bên phải của nút, v)
giảm v [val of node] đi 1
Từ phương thức chính, thực hiện như sau -
ret:=0
Xác định cnt mảng có kích thước 10
dfs (root, cnt)
trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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));
}

Đầu vào

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

Pseudo-Palindromic Path in a Binary Tree in C ++

Ví dụ

Đầu vào

Đầu ra