1457. Pseudo-Palindromic PAths in a Binary Tree

link

Idea

Outline

• store as pair number in stack with corresponding node, shown as bit
• ex: {2,0} {3,4} {1,4} {3,12} {1,12} {1,6}
• for {2,0}: since 2 is root, we give it path=0
  
  
• for other branch like {3,4}: we give it path= parent-path ^ (1<<parent-value), that is,
  
  $$1<<2=1shiftleft2bit={100}_2=4_{10}$$
  
  
• for leaf nodes like {3,12}
  
  
  • we give it path= parent-path ^ (1<<parent-value)
  • and check if path&(path-1)==0

Step

1. keep a stack to traverse the tree using DFS
2. store current-path ^ current->value to children node and put these children to stack every time
3. if arrive the leaf(no left and right child), we check if the path&(path-1)==0,
   • we want to check if there's only one set when the number represented in bit form
   • ex: 0100 will be accepted because
     $0100\mathrm{\&}0011=0000$
   • ex: 1111 will be rejected because
     $1111\mathrm{\&}1110=1110$

Why keep current-path ^ current->value as frequency count?

1. Take 2-3-3 this path for example
   
   
2. appear even time: after Xor operation, digit=0
3. appear odd time: after Xor operation, digit=1
4. Since only when there's at most one element has odd frequency in a list can form a palindrome, we keep the count of element in the path. Then check the count when we arrived leaf

Reference

bit shift