-
Notifications
You must be signed in to change notification settings - Fork 277
/
Copy pathPseudoPalindromicPathsInABinaryTree.java
87 lines (66 loc) · 1.91 KB
/
PseudoPalindromicPathsInABinaryTree.java
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Solution {
private int ans = 0;
// TC : O(n)
// SC : O(n) *10
public int pseudoPalindromicPaths (TreeNode root) {
int[] freq = new int[10];
helper(root, freq);
return ans;
}
private void helper(TreeNode root, int[] freq){
if(root== null){
return ;
}
freq[root.val]++;
if(root.left == null && root.right == null){
// this is a leaf node
if(isPalindromicPermutation(freq)){
ans++;
}
}
helper(root.left, freq);
helper(root.right, freq);
freq[root.val]--;
}
private boolean isPalindromicPermutation(int[] freq){
boolean oddFreqFound = false;
for(int el: freq){
if(el%2!=0){
if(oddFreqFound){
return false;
} else{
oddFreqFound = true;
}
}
}
return true;
}
}
================ Approach using Bit Masking =================
// https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/
// @author: anuj0503
class Solution {
int result;
Set<Integer> set;
public int pseudoPalindromicPaths (TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return 1;
set = new HashSet<>();
for(int i = 1; i <= 9; i++){
set.add((int) Math.pow(2, i));
}
set.add(0);
result = 0;
getResult(root, 0);
return result;
}
private void getResult(TreeNode root, int mask){
if(root == null) return;
if(root.left == null && root.right == null){
if(set.contains(mask ^ (1 << root.val))) result++;
} else {
getResult(root.left, mask ^ (1 << root.val));
getResult(root.right, mask ^ (1 << root.val));
}
}
}