当前位置：网站首页>[binary tree] pseudo palindrome path in binary tree

[binary tree] pseudo palindrome path in binary tree

2022-07-28 22:17:00 【How cold it is】

0x00 subject

Here is a binary tree for you , The value of each node is 1 To 9
We call a path in a binary tree 「 Pseudo palindrome 」 Of
When it satisfies ： In the arrangement of all node values that the path passes through
There is One Palindrome Sequence

Please return from root To leaf All paths of nodes
Pseudo palindrome The path of number

0x01 Ideas

A palindrome number has the following characteristics ：
Situation 1 ：1221, Numbers frequency yes even numbers Time
Situation two ：121, Only One The numbers appear Odd number Time
XOR operation based on bit operation ： Any number n
n ^ n = 0
Can pass Exclusive or operation eliminate Even numbers

The range of topics is 1～9 So it can be used every Represents a number
3 Expressed as ：000000100
5 Expressed as ：000010000
If the last remaining number is 3 and 5
So that is ： 000010100
Yes 2 individual 1, Even number of times
therefore No It's palindrome number
Through the loop Move right and And operation To calculate how many 1
(10100 >> 1) & 1

And more Simple The way to ：
Any number ：n
Bit operation And operation &
n & (n - 1) = 0
10100 &
10011 =
10000
Why not 0

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func pseudoPalindromicPaths (_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    var res: Int = 0
    
    func dfs(_ root: TreeNode?, _ val: Int) {
        guard let root = root else { return }
        
        //  Exclusive or operation 
        let n = val ^ (1 << root.val)
        //  Leaf node 
        if root.left == nil && root.right == nil {
            //  All even numbers , It's all eliminated 
            //  Or just one number left 
            if n == 0 || (n & (n-1)) == 0 {
                res += 1
            }
            return
        }
        
        //  Recursive left and right subtrees 
        if let left = root.left {
            dfs(left, n)
        }
        if let right = root.right {
            dfs(right, n)
        }
    }

    dfs(root, 0)
    return res
}