[leetcode] 1457. Pseudo-Palindromic Paths in a Binary Tree

Int Array

class Solution {
    var answer = 0
    
    fun pseudoPalindromicPaths (root: TreeNode?): Int {
        val digit = IntArray(10) { 0 }
    
        dfs(root, digit)
        
        return answer
    }
    
    fun dfs(root: TreeNode?, digit: IntArray) {
        if (root == null) return
    
        digit[root.`val`]++
        
        if (root.left == null && root.right == null) {
            var odd = 0
            
            for (i in 1 until 10) {
                if (digit[i] % 2 == 1) odd++
            }
            
            if (odd == 1 || odd == 0) answer++   
            
            return
        }
    
        dfs(root.left, digit)        
        if (root.left != null) digit[root.left.`val`]--
        dfs(root.right, digit)       
        if (root.right != null) digit[root.right.`val`]--
    }
}

Hash Set

class Solution {
    
    fun pseudoPalindromicPaths (root: TreeNode?): Int {        
        return dfs(root, hashSetOf())        
    }
    
    fun dfs(root: TreeNode?, nums: HashSet<Int>): Int {
        if (root == null) return 0
    
        if (nums.contains(root.`val`)) nums.remove(root.`val`)
        else nums.add(root.`val`)
        
        if (root.left == null && root.right == null) {
            return if (nums.size <= 1) 1
            else 0
        }
        
        val left = dfs(root.left, HashSet(nums))
        val right = dfs(root.right, HashSet(nums))
        
        return left + right
    }
}

bit manipulation

class Solution {
    
    fun pseudoPalindromicPaths (root: TreeNode?): Int {        
        return dfs(root, 0)        
    }
    
    fun dfs(root: TreeNode?, bit: Int): Int {
        if (root == null) return 0
        
        val temp = bit.xor(1.shl(root.`val` - 1))
        var answer = dfs(root.left, temp) + dfs(root.right, temp)
        if (root.left == null && root.right == null && (temp == 0 || temp.and(temp - 1) == 0)) answer++
        return answer
    }  
}