Leetcode 1457. Pseudo-Palindromic Paths in a Binary Tree (python)

题目

解法1：

利用backtracking生成每条根节点到叶结点的路径，在利用字典注意判断。一条路径的permutaion要可以回文的条件是奇数个的数字个数只能是0或1

class Solution:def pseudoPalindromicPaths (self, root: TreeNode) -> int:def dfs(node,path):if not node:returnpath.append(node.val)if not node.left and not node.right:paths.append(path[:])dfs(node.left,path[:])dfs(node.right,path[:])path.pop()paths = []path = []dfs(root,path)ans = 0for path in paths:dic = collections.defaultdict(int)for v in path:dic[v]+=1odd = 0for v in dic.values():if v%2!=0:odd += 1if odd == 0 or odd == 1:ans += 1return ans

解法2：

实际上不用生成每条路径，在dfs的时候直接backtracking保存数字个数的字典就可以了

class Solution:def pseudoPalindromicPaths (self, root: TreeNode) -> int:def dfs(node):nonlocal ansif not node:returnd[node.val]+=1if not node.left and not node.right:odd = 0for k,v in d.items():if v%2 != 0:odd += 1if odd==0 or odd==1:ans += 1dfs(node.left)dfs(node.right)d[node.val] -= 1d = collections.defaultdict(int)ans = 0dfs(root)return ans

c++版本

class Solution {
    
public:void helper(int& ans,TreeNode* node,vector<int>& memo){
    if(!node) return;memo[node->val]++;// cout << node->val << "#" << endl;// for(int i=1;i<=9;i++) cout << memo[i] << endl;if(!node->left && !node->right){
    int cnt = 0;for(int i=1;i<=9;i++){
    if(memo[i]%2 != 0) cnt++;}if(cnt <= 1) {
    ans++;// cout << node->val << endl;}// memo[node->val]++;// return;}helper(ans,node->left,memo);helper(ans,node->right,memo);memo[node->val]--;return;}int pseudoPalindromicPaths (TreeNode* root) {
    int ans = 0;vector<int> memo(10,0);helper(ans,root,memo);return ans;}
};

时间复杂度： O(n*k), n为节点个数，k为9代表9个数字
空间复杂度：O(k+h),h为树的深度

二刷：解法3，利用set

利用set的特性来保证是否valid，如果当前值已经出现过，代表加上现在的是偶数，可以把这个元素从set中移除，反之将这个元素加入set。最后通过set的长度来判断，因为只有出现过奇数次的元素会留在set

class Solution {
    
public:void helper(int& ans,TreeNode* node,unordered_set<int>& memo){
    if(!node) return;if(memo.count(node->val)) {
    memo.erase(node->val);}else{
    memo.insert(node->val);}if(!node->left && !node->right){
    if(memo.size() <= 1) {
    ans++;// cout << node->val << endl;}// memo[node->val]++;// return;}helper(ans,node->left,memo);helper(ans,node->right,memo);if(memo.count(node->val)) {
    memo.erase(node->val);}else{
    memo.insert(node->val);}return;}int pseudoPalindromicPaths (TreeNode* root) {
    int ans = 0;unordered_set<int> memo;helper(ans,root,memo);return ans;}
};

时间复杂度： O(n), n为节点个数
空间复杂度：O(k+h),h为树的深度
照理来说这种解法时间复杂度更优，但是实际上提交结果更差，其中原因有可能是set的查找，增加和删除元素实际上没有这么快