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 {
private int ans = 0;
private int oddCount = 0;
public int pseudoPalindromicPaths(TreeNode root) {
helper(root, new int[10]);
return ans;
}
private void helper(TreeNode node, int[] numCount) {
if (node == null) {
return;
}
int offset = numCount[node.val] % 2 == 1 ? -1 : 1;
numCount[node.val] += 1;
oddCount += offset;
helper(node.left, numCount);
helper(node.right, numCount);
if (node.left == null && node.right == null && oddCount <= 1) {
ans += 1;
}
numCount[node.val] -= 1;
oddCount -= offset;
}
}
|
用array记录每个数字出现的次数. post-order traversal(pre-order也可以). 我们是边走边记录从root到当前位置的node的path上node.val出现的频率. 到达leaf node的时候看是否最多只有一个num的频率是奇数次.
时间复杂度: O(9N) = O(N) 假设是个perfect tree, 那leaf node的个数与总共nodes的个数是一个数量级的, 因此是O(9N). 因为我们在leaf node要遍历数组.
空间复杂度: O(N) 递归需要用栈.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
private int ans = 0;
public int pseudoPalindromicPaths(TreeNode root) {
helper(root, 0);
return ans;
}
private void helper(TreeNode node, int path) {
if (node == null) {
return;
}
path ^= 1 << node.val;
helper(node.left, path);
helper(node.right, path);
if (node.left == null && node.right == null && (path & (path - 1)) == 0) {
ans += 1;
}
}
}
|
lee哥的解法使用一个integer来存1-9出现的次数. 偶数的话会抵消, 奇数的话, 对应的位置就是1. 那我们如何快速知道有奇数个1还是偶数个1? 好的方法就是num & (num - 1). 这个方法牢记.
有个问题是path更新完后, 为什么不返回原状? 因为这里path是local variable, 上一层保留了修改前的path的值. 因此就不需要我们把此时的path给改回去了.
时间复杂度: O(n)
空间复杂度: O(n)
