Đường đi giả đối xứng trong cây nhị phân (Pseudo-Palindromic Paths in a Binary Tree) trong C++

Cho cây nhị phân các nút mang giá trị 1-9. Một đường đi từ gốc đến lá gọi là giả đối xứng (pseudo-palindromic) nếu có thể hoán vị các giá trị trên đường đi thành một xâu đối xứng (palindrome). Điều kiện: tối đa một chữ số xuất hiện số lẻ lần. Đếm số đường đi như vậy.

Ví dụ

Đầu ra: 2 (đường [2,3,3] và [2,1,1]).

Thuật toán DFS + Bitmask

1. Duyệt DFS từ gốc đến lá, truyền mảng đếm tần suất 10 phần tử (hoặc bitmask 10 bit).
2. Tại nút lá: kiểm tra số bit 1 trong bitmask ≤ 1 → tăng kết quả.
3. Backtrack: giảm tần suất / xor bit khi quay lui.

Triển khai C++ (Bitmask tối ưu)

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

class Solution {
    int ans = 0;
    void dfs(TreeNode* node, int mask) {
        if (!node) return;
        mask ^= (1 << node->val); // toggle bit
        if (!node->left && !node->right) {
            // check at most one bit set
            if ((mask & (mask - 1)) == 0) ans++;
        }
        dfs(node->left, mask);
        dfs(node->right, mask);
    }
public:
    int pseudoPalindromicPaths(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt mỗi nút một lần.
• Không gian: O(H) - ngăn xếp đệ quy, H chiều cao cây.

Kết quả kiểm thử

Đầu vào: {2,3,1,3,1,NULL,1}
Đầu ra: 2