1457. Pseudo-Palindromic Paths in a Binary Tree

, ,

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
class Solution {
    public int pseudoPalindromicPaths(TreeNode root) {
        int[] countMap = new int[10];
        return dfs(root, countMap);
    }

    private int dfs(TreeNode node, int[] countMap) {
        int pathCount = 0;
        countMap[node.val]++;

        if (node.left == null && node.right == null) {
            // node is leaf
            int oddCount = 0;
            for (int c : countMap) {
                if ((c & 1) == 1) {
                    oddCount++;
                }
            }
            pathCount += oddCount <= 1 ? 1 : 0;
        }

        if (node.left != null) {
            pathCount += dfs(node.left, countMap);
        }
        if (node.right != null) {
            pathCount += dfs(node.right, countMap);
        }
        countMap[node.val]--;
        return pathCount;
    }
}

DFS + Bit

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
class Solution {
    public int pseudoPalindromicPaths(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int countMask) {
        int pathCount = 0;
        countMask ^= 1 << node.val;

        if (node.left == null && node.right == null) {
            // node is leaf
            if (countMask == (countMask & -countMask)) { // 仅有一个 bit 为 1
                pathCount++;
            }
        }

        if (node.left != null) {
            pathCount += dfs(node.left, countMask);
        }
        if (node.right != null) {
            pathCount += dfs(node.right, countMask);
        }
        return pathCount;
    }
}

References

1457. Pseudo-Palindromic Paths in a Binary Tree