1457.pseudo-palindromic-paths-in-a-binary-tree.md

1457. Pseudo-Palindromic Paths in a Binary Tree

DFS

How can we check if path is pseudo-palindromic? There are at most one digit with an odd frequency.

private var count = 0
    
fun pseudoPalindromicPaths(root: TreeNode?): Int {
    dfs(root, IntArray(10))
    return count
}

private fun dfs(root: TreeNode?, digits: IntArray) {
    if (root == null) return
    digits[root.`val`]++
    if (root.left == null && root.right == null) {
        if (digits.isPal()) count++
        digits[root.`val`]--
        return
    }
    dfs(root.left, digits)
    dfs(root.right, digits)
    digits[root.`val`]--
}

private fun IntArray.isPal(): Boolean {
    var total = 0
    var even = 0
    var odd = 0
    for (i in 0 until this.size) {
        if (this[i] == 0) continue
        total += this[i]
        if (this[i] % 2 == 0) even++
        else odd++
    }
    return if (total % 2 == 0) {
        // All counts should be even
        odd == 0
    } else {
        // Allow only one odd
        odd == 1
    }
}

• Time Complexity: O(n).
• Space Complexity: O(h) to store the path.