【二叉树】二叉树中的伪回文路径

0x00 题目

给你一棵二叉树，每个节点的值为 1 到 9
我们称二叉树中的一条路径是 「伪回文」的
当它满足：路径经过的所有节点值的排列中
存在一个回文序列

请你返回从根到叶子节点的所有路径中
伪回文 路径的数目

---

0x01 思路

一个回文数有以下特征：
情况一：1221，数字次数是偶数次
情况二：121，只有一个数字出现奇数次
根据位运算的异或运算：任何一个数 n
n ^ n = 0
可以通过异或运算消除偶数次的数

题目取值范围是1～9 所以可以用每一位代表一个数字
3表示为：000000100
5表示为：000010000
如果最后剩下的数是 3 和 5
那么就是： 000010100
有 2 个 1，偶数次
所以不是回文数
通过循环 右移 和 与运算来计算有多少个 1
(10100 >> 1) & 1

还有更简单的办法：
任何一个数：n
通过位运算 与运算&
n & (n - 1) = 0
10100 &
10011 =
10000
为不 0

---

0x02 解法

语言：Swift

树节点：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
    }
}

解法：

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 }
        
        // 异或运算
        let n = val ^ (1 << root.val)
        // 叶子节点
        if root.left == nil && root.right == nil {
            // 所有偶数次的数，都消除了
            // 或者只剩下一个数
            if n == 0 || (n & (n-1)) == 0 {
                res += 1
            }
            return
        }
        
        // 递归左右子树
        if let left = root.left {
            dfs(left, n)
        }
        if let right = root.right {
            dfs(right, n)
        }
    }

    dfs(root, 0)
    return res
}

---

0x03 我的小作品

欢迎体验我的作品之一：小五笔 86 版
五笔学习好帮手
App Store 搜索即可~

---