网站规范建设情况,百度搜索引擎算法,竞价账户托管哪家好,网站建设 推广信息原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
耗时#xff1a;28min48s
C代码 dfs、二叉树前序遍历、哈希表记录 #includebits/stdc.h
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *rig…原题链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
耗时28min48s
C代码 dfs、二叉树前序遍历、哈希表记录 #includebits/stdc.h
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};class Solution {
public:mapint,inthash;bool check(){//检查该路是否符合伪回文数int cnt 0;for(auto it:hash){if(it.second % 2 ! 0) cnt;if(cnt1) return false; }return true;}int pseudoPalindromicPaths (TreeNode* root) {if(root nullptr) return 0;coutroot-val ;if(!hash.count(root-val)) hash[root-val] 1;else hash[root-val];int left pseudoPalindromicPaths(root-left);if(root-left nullptr root-right nullptr){//叶子结点int flag 0;if(check()){flag 1;}hash[root-val]--;if(hash[root-val] 0) hash.erase(root-val);return flag;}int right pseudoPalindromicPaths(root-right);//回溯删除哈希表中的记录hash[root-val]--;if(hash[root-val] 0) hash.erase(root-val);return leftright;}
};C为check函数运行时间 n为二叉树结点个数 时间复杂度O(C*n) 空间复杂度O(n) Python代码 位运算效率高奇思妙想 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def pseudoPalindromicPaths (self, root: Optional[TreeNode]) - int:ans 0def lowbit(cnt): return cnt -cntdef dfs(root,cnt):nonlocal ansif not root.left and not root.right:cnt ^ 1 root.valif cnt lowbit(cnt):ans 1returnif root.left:dfs(root.left,cnt^(1root.val))if root.right:dfs(root.right,cnt^(1root.val))dfs(root,0)return ans
