diff options
Diffstat (limited to 'palindromic_paths_bt.py')
-rw-r--r-- | palindromic_paths_bt.py | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/palindromic_paths_bt.py b/palindromic_paths_bt.py new file mode 100644 index 0000000..1f65c94 --- /dev/null +++ b/palindromic_paths_bt.py @@ -0,0 +1,45 @@ +# 1457. 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. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def pseudoPalindromicPaths(self, root): + """ + :type root: TreeNode + :rtype: int + """ + if not root: + return 0 + count ^= 1 << (root.val - 1) + res = self.pseudoPalindromicPaths( + root.left, count + ) + self.pseudoPalindromicPaths(root.right, count) + if root.left == root.right: + if count & (count - 1) == 0: + res += 1 + return res + + +if __name__ == "__main__": + obj = Solution() + print(obj.pseudoPalindromicPaths(root=[2, 3, 1, 3, 1, null, 1])) + print( + obj.pseudoPalindromicPaths( + root=[2, 1, 1, 1, 3, null, null, null, null, null, 1] + ) + ) + print(obj.pseudoPalindromicPaths(root=[9])) |