เส้นทางปลอมแพลินโดรมใน Binary Tree ใน C++

สมมติว่าเรามี binary tree ที่ค่าโหนดเป็นเลข 1-9 เส้นทางถือว่า pseudo-palindromic ถ้ามีการเรียงลำดับใหม่ของค่าในเส้นทางที่เป็น palindrome เราต้องนับจำนวนเส้นทางแบบนี้จาก root ถึง leaf

ตัวอย่าง: ต้นไม้ที่มีเส้นทาง [2,3,3], [2,1,1], [2,3,1] ผลลัพธ์ = 2 (เส้นทางแรกและสองเป็น pseudo-palindromic)

วิธีแก้ปัญหา (DFS + Bitmask/Count)

1. DFS จาก root ถึง leaf
2. นับความถี่ตัวเลข 1-9 ใน path ปัจจุบัน
3. ที่ leaf: ตรวจสอบว่าเลขคี่มีได้สูงสุด 1 ตัว (เงื่อนไข palindrome)
4. Backtrack: ลบ count เมื่อย้อนกลับ

ตัวอย่างโค้ด C++

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

int 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}

ผลลัพธ์

2