LeetCode Entry

1457. Pseudo-Palindromic Paths in a Binary Tree

24.01.2024 medium 2024 kotlin rust

Count can-form-a-palindrome paths root-leaf in a binary tree.

1457. Pseudo-Palindromic Paths in a Binary Tree medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/482

Problem TLDR

Count can-form-a-palindrome paths root-leaf in a binary tree.

Intuition

Let’s walk a binary tree with Depth-First Search and check the frequencies in path’s numbers. To form a palindrome, only a single frequency can be odd.

Approach

  • only odd-even matters, so we can store just boolean flags mask

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\)

Code


  fun pseudoPalindromicPaths (root: TreeNode?): Int {
    fun dfs(n: TreeNode?, freq: Int): Int = n?.run {
      val f = freq xor (1 shl `val`)
      if (left == null && right == null) {
        if (f and (f - 1) == 0) 1 else 0
      } else dfs(left, f) + dfs(right, f)
    } ?: 0
    return dfs(root, 0)
  }



  pub fn pseudo_palindromic_paths (root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, freq: i32) -> i32 {
      n.as_ref().map_or(0, |n| {
        let n = n.borrow();
        let f = freq ^ (1 << n.val);
        dfs(&n.left, f) + dfs(&n.right, f) +
          (n.left.is_none() && n.right.is_none() && (f & (f - 1) == 0)) as i32
      })
    }
    dfs(&root, 0)
  }