Medium

题目描述

给你一棵二叉树，每个节点的值为 1 到 9 的数字。如果从根节点到某个叶子节点路径上的所有节点值的至少一个排列构成回文，则该路径被称为伪回文路径。

返回从根节点到叶子节点的伪回文路径数目。

示例 1：

输入：root = [2,3,1,3,1,null,1]
输出：2 
解释：上图是给定的二叉树。有三条从根节点到叶子节点的路径：红色路径 [2,3,3]、绿色路径 [2,1,1] 和路径 [2,3,1]。在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3]，绿色路径 [2,1,1] 存在回文排列 [1,2,1]。

示例 2：

输入：root = [2,1,1,1,3,null,null,null,null,null,1]
输出：1 
解释：上图是给定的二叉树。有三条从根节点到叶子节点的路径：绿色路径 [2,1,1]、路径 [2,1,3,1] 和路径 [2,1]。在这些路径中，只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1]。

示例 3：

输入：root = [9]
输出：1

约束条件：

  • 树中节点数目在范围 [1, 10^5] 内
  • 1 <= Node.val <= 9

解题思路

解题思路

这道题要求统计从根到叶子的路径中，有多少条路径的节点值能重新排列成回文数。关键是理解什么情况下一组数字能组成回文：最多只能有一个数字出现奇数次。

核心思想

  1. 使用深度优先搜索(DFS)遍历所有从根到叶子的路径
  2. 在遍历过程中统计每个数字(1-9)的出现次数
  3. 到达叶子节点时，检查是否最多只有一个数字出现奇数次

优化技巧

由于只需要关心奇偶性，可以使用位运算优化：

  • 用一个整数的10个位来记录数字1-9的奇偶状态
  • 每遇到一个数字就异或对应位，奇数次为1，偶数次为0
  • 检查时只需判断有多少位为1（使用 x & (x-1) 技巧快速统计）

算法步骤

  1. 从根节点开始DFS，维护当前路径的数字奇偶状态
  2. 遇到节点时更新对应数字的状态
  3. 到达叶子节点时检查状态，最多一位为1则是伪回文路径
  4. 回溯时恢复状态，继续搜索其他路径

推荐解法：位运算DFS，时空复杂度最优。

代码实现

class Solution {
public:
    int pseudoPalindromicPaths(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int freq) {
        if (!node) return 0;
        
        // 更新当前数字的奇偶状态
        freq ^= (1 << node->val);
        
        // 如果是叶子节点，检查是否为伪回文
        if (!node->left && !node->right) {
            // 最多只能有一个数字出现奇数次
            return (freq & (freq - 1)) == 0 ? 1 : 0;
        }
        
        // 递归处理左右子树
        return dfs(node->left, freq) + dfs(node->right, freq);
    }
};

class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        def dfs(node, freq):
            if not node:
                return 0
            
            # 更新当前数字的奇偶状态
            freq ^= (1 << node.val)
            
            # 如果是叶子节点，检查是否为伪回文
            if not node.left and not node.right:
                # 最多只能有一个数字出现奇数次
                return 1 if (freq & (freq - 1)) == 0 else 0
            
            # 递归处理左右子树
            return dfs(node.left, freq) + dfs(node.right, freq)
        
        return dfs(root, 0)

public class Solution {
    public int PseudoPalindromicPaths(TreeNode root) {
        return Dfs(root, 0);
    }
    
    private int Dfs(TreeNode node, int freq) {
        if (node == null) return 0;
        
        // 更新当前数字的奇偶状态
        freq ^= (1 << node.val);
        
        // 如果是叶子节点，检查是否为伪回文
        if (node.left == null && node.right == null) {
            // 最多只能有一个数字出现奇数次
            return (freq & (freq - 1)) == 0 ? 1 : 0;
        }
        
        // 递归处理左右子树
        return Dfs(node.left, freq) + Dfs(node.right, freq);
    }
}

var pseudoPalindromicPaths = function(root) {
    let count = 0;
    
    function dfs(node, path) {
        if (!node) return;
        
        path ^= (1 << node.val);
        
        if (!node.left && !node.right) {
            if ((path & (path - 1)) === 0) {
                count++;
            }
        } else {
            dfs(node.left, path);
            dfs(node.right, path);
        }
    }
    
    dfs(root, 0);
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n为树中节点数，需要访问每个节点一次
空间复杂度O(h)h为树的高度，递归调用栈的深度