#1457
Pseudo-Palindromic Paths in a Binary Tree
pupil · 580 · lc medium +29 · verified · 68.4% accepted · 3,339 likes · top 75%
Description
Each node in a binary tree holds a digit from 1 to 9. A root-to-leaf path is called pseudo-palindromic if its node values can be rearranged to form a palindrome. Count and return the total number of pseudo-palindromic root-to-leaf paths.
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
Code
1
2
3
4
5
6
7
8
9