2022-09-14 Daily-Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 14

Description

Pseudo-Palindromic Paths in a Binary Tree

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:

img

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:

img

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, 10^5].
  • 1 <= Node.val <= 9

Solution

class Solution {
  bool parity[10] = {0};
  int answer = 0;
  int odd = 0;
  void helper(TreeNode *root) {
    parity[root->val] ^= 1;
    if(parity[root->val]) odd += 1;
    else odd -= 1;
    if(!(root->left) && !(root->right)) answer += (odd < 2);
    if(root->left) helper(root->left);
    if(root->right) helper(root->right);
    if(parity[root->val]) odd -= 1;
    else odd += 1;
    parity[root->val] ^= 1;
  }
public:
  int pseudoPalindromicPaths (TreeNode* root) {
    helper(root);
    return answer;
  }
};

// Accepted
// 56/56 cases passed (675 ms)
// Your runtime beats 38.56 % of cpp submissions
// Your memory usage beats 92.41 % of cpp submissions (179.1 MB)
Algorithm