Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1] Output: 2

Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1] Output: 1

Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9] Output: 1

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 9

题目分析

DFS, Hash Table, Bit Manipulation

代码实现

DFS | Bit Manipulation

class Solution {
public:
    int cnt;
    void dfs(TreeNode* r, int st) {
        if(!r->left && !r->right) {
            int t = (st ^ (1 << r->val));
            cnt += !(t - (t & -t));
            return ;
        }
        if(r->left) dfs(r->left, st ^ (1 << r->val));
        if(r->right) dfs(r->right, st ^ (1 << r->val));
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        dfs(root, 0);
        return cnt;
    }
};

DFS | Hash Table

 #define x first
 #define y second
class Solution {
public:
    int cnt;
    unordered_map <int,int> st;
    bool check() {
        int t = 0;
        for(auto& p : st) {
            if(p.y & 1) ++t;
            if(t == 2) return 0;
        }
        return 1;
    }
    void dfs(TreeNode* r) {
        ++st[r->val];
        if(!r->left && !r->right) {
            cnt += check();
            --st[r->val];
            return ;
        }
        if(r->left) dfs(r->left);
        if(r->right) dfs(r->right);
        --st[r->val];

    }
    int pseudoPalindromicPaths (TreeNode* root) {
        dfs(root);
        return cnt;
    }
};

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status