『LeetCode』1457 二叉树中的伪回文路径

题目

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

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

示例 1：

输入：root = [2,3,1,3,1,null,1]
输出：2解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [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解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [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\)

题解

【二叉树中的伪回文路径】DFS与位运算

DFS

题目中对 「伪回文」 的定义是：数值的排列中存在一个回文序列。不难想到要用统计的方法判断是否是“伪回文”，具体而言：

若序列是偶数，那么所有的字符出现次数得是偶数次
若序列是奇数，那么允许有一个字符出现次数是奇数（放回文序列的中心）

对于树形结构，DFS与BFS是优先考虑的算法，这里需要得到路径，显然使用 DFS 更合适。

我们使用 DFS 遍历二叉树并使用回溯的方法统计到根节点的路径，若遍历到叶子节点则判断是否是伪回文。

# Code language: Python
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        cnts = [0] * 10
        def dfs(root):
            if not root:
                return 0
            cnts[root.val] += 1
            if not root.left and not root.right:
                if sum(v % 2 for v in cnts) > 1:
                    ans = 0
                else:
                    ans = 1
            else:
                ans = dfs(root.left) + dfs(root.right)
            cnts[root.val] -= 1
            return ans
        return dfs(root)

// Code language: Java
class Solution {
    public int pseudoPalindromicPaths (TreeNode root) {
        return dfs(root, new int[10]);
    }

    public int dfs(TreeNode root, int[] cnts) {
        if (root == null) return 0;
        cnts[root.val]++;
        int ans;
        if (root.left == null && root.right == null) {
            int v = 0;
            for (int i = 0; i < 10; i++) {
                if (cnts[i] % 2 == 1) v++;
            }
            ans = v > 1 ? 0 : 1;
        }
        else {
            ans = dfs(root.left, cnts) + dfs(root.right, cnts);
        }
        cnts[root.val]--;
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    int pseudoPalindromicPaths (TreeNode* root) {
        vector<int> cnts(10, 0);
        return dfs(root, cnts);
    }

    int dfs(TreeNode* root, vector<int>& cnts) {
        if (root == nullptr) return 0;
        cnts[root->val]++;
        int ans;
        if (root->left == nullptr && root->right == nullptr) {
            int v = 0;
            for (int i = 0; i < 10; i++) {
                if (cnts[i] % 2 == 1) v++;
            }
            ans = v > 1 ? 0 : 1;
        }
        else {
            ans = dfs(root->left, cnts) + dfs(root->right, cnts);
        }
        cnts[root->val]--;
        return ans;
    }
};

/* Code language: Go */
func dfs(cur *TreeNode, cnts [10]int) int {
    if cur == nil {
        return 0
    }
    cnts[cur.Val]++
    // 叶子节点
    if cur.Left == nil && cur.Right == nil {
        v := 0
        for _, j := range cnts {
            if j%2 == 1 {
                v++
            }
        }
        if v <= 1 {
            return 1
        }
        return 0
    }
    // 非叶结点
    return dfs(cur.Left, cnts) + dfs(cur.Right, cnts)
}

func pseudoPalindromicPaths(root *TreeNode) int {
    // Go 的函数是值传递，就不用回溯了
    return dfs(root, [10]int{})
}

时间复杂度: \(O(nC)\)，其中树中节点的数量为 \(n\)，节点值的取值范围 \(C=10\)
空间复杂度: \(O(n)\), 递归函数需要至多 \(O(n)\) 的栈空间

位运算

事实上我们统计各个数值的出现次数是否为奇数即可，可以使用一个整型数代替原有的统计数组，第 \(i\) 位的值为 1 表示 \(i\) 出现了奇数次。再统计 1 出现的次数是否大于 1 即可判断序列是否为伪回文。

常用 x & (-x) 或 x & (x - 1) 消去 x 中最低位的 1，这里可以用于判断 1 的出现次数。

# Code language: Python
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        def dfs(root, cnts):
            if not root:
                return 0
            cnts ^= 1 << root.val
            if not root.left and not root.right:
                if cnts & (cnts - 1) != 0:
                    ans = 0
                else:
                    ans = 1
            else:
                ans = dfs(root.left, cnts) + dfs(root.right, cnts)
            return ans
        return dfs(root, 0)

// Code language: Java
class Solution {
    public int pseudoPalindromicPaths (TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int cnts) {
        if (root == null) return 0;
        cnts ^= 1 << root.val;
        if (root.left == null && root.right == null) {
            return (cnts & (cnts - 1)) != 0 ? 0 : 1;
        }
        return dfs(root.left, cnts) + dfs(root.right, cnts);
    }
}

// Code language: C++
class Solution {
public:
    int pseudoPalindromicPaths (TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode *root, int cnts) {
        if (root == nullptr) return 0;
        cnts ^= 1 << root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return (cnts & (cnts - 1)) != 0 ? 0 : 1;
        }
        return dfs(root->left, cnts) + dfs(root->right, cnts);
    }
};

/* Code language: Go */
func dfs(cur *TreeNode, cnts int) int {
    if cur == nil {
        return 0
    }
    cnts ^= 1 << cur.Val
    // 叶子节点
    if cur.Left == nil && cur.Right == nil {
        if cnts & (cnts - 1) == 0 {
            return 1
        }
        return 0
    }
    // 非叶结点
    return dfs(cur.Left, cnts) + dfs(cur.Right, cnts)
}
func pseudoPalindromicPaths(root *TreeNode) int {
    return dfs(root, 0)
}

时间复杂度: \(O(n)\)，其中树中节点的数量为 \(n\)
空间复杂度: \(O(n)\), 递归函数需要至多 \(O(n)\) 的栈空间

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1457 二叉树中的伪回文路径

题目

标签

题解

DFS

位运算