leetcode周赛5418.二叉树中的伪回文路径

leetcode周赛5418.二叉树中的伪回文路径

六月 26, 2020

leetcode周赛5418.二叉树中的伪回文路径

给你一棵二叉树，每个节点的值为 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] 。

dfs

具体思路见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    /*因为数字顺序可以调换，所以只需要看序列里面的每个数字出现的次数，是奇数，偶数就行
    回文串里面奇数次数只能最多有一个，偶数随意
    */
    //开始没看到只有九个数字，所以用了map，和count计数，我怕数字多了，map遍历上面浪费时间
    public int count = 0;//记录奇数出现几次，偶数出现几次
    public int ans = 0;
    public HashMap<Integer,Integer> map = new HashMap<>(1024);
    public int pseudoPalindromicPaths (TreeNode root) {
        dfs(root);
        return ans;
    }
    public void dfs(TreeNode root) {
        int v = map.getOrDefault(root.val,0);
        v++;
        int t = count;
        if ((v & 1) == 1) {//当前数字出现次数是奇数
            count++;
        } else {//是偶数
            count--;
        }
        map.put(root.val,v);
        if (root.left == null && root.right == null) {
            //到达叶节点
            if (count <= 1) {
                ans++;
            }
        }
        if (root.left != null)
        dfs(root.left);
        if (root.right != null)
        dfs(root.right);
        //回溯，恢复状态
        map.put(root.val,v - 1);
        count = t;
    }
}

这次周赛半个小时就写完前三题，第四题只知道是dp，怎么dp就不清楚了。残念~。
leetcode 104