#1457. Pseudo-Palindromic Paths in a Binary Tree

https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/description/?envType=daily-question&envId=2024-01-24

function pseudoPalindromicPaths(root) {

    function isPalindrome(frequencies) {
        let oddCount = 0
        for (let frequency of frequencies) {
            if (frequency % 2 === 1) {
                oddCount++
            }
        }
        return oddCount < 2
    }

    let result = 0

    function dfs(node, frequencies) {
        if (!node) return

        frequencies[node.val]++

        if (!node.left && !node.right) {
            if (isPalindrome(frequencies)) result++
        } else {
            dfs(node.right, [...frequencies])
            dfs(node.left, [...frequencies])
        }
    }

    const frequencies = new Array(10).fill(0)
    dfs(root, frequencies)
    return result
}

This seems hard initially but its actually simple. The idea is, we a binary tree and from the root to every leave, we check if the values is a palindrome.

NOTE: A palindrome is a word, sentence, verse, or even number that reads the same backward or forward.

Firstly, we write an helper function that check is a series of number is palindrome. The algorithm is, at most, one number of a series must be odd and the rest even.

3,1,3 is a palindrome. It has one odd number

3,2,2,3 is a palindrome. It has zero odd number.

3,1,2,3 is not a palindrome. It has two odd numbers.

Thereafter, we create a result variable that counts the number of palindrome.

Then the dfs() function iterate through the tree and count the occurrence of each number in a subtree, when it gets to the leaf node, it checks if the subtree is a palindrome then returns if there are no more nodes to traverse.

It then check the left and right children of a node with a copy of the frequency array. Lastly, the result is returned.