网站建设与优化标准,wordpress脚本,东平县建设局信息网站,西安百度推广公司文章目录 Tag题目来源题目解读解题思路方法一#xff1a;递归#xff08;DFS#xff09;方法二#xff1a;位运算 写在最后 Tag
【递归/DFS】【伪回文】【二叉树】【2023-11-25】 题目来源
1457. 二叉树中的伪回文路径 题目解读
伪回文路径指的是路径中的节点值经过重新… 文章目录 Tag题目来源题目解读解题思路方法一递归DFS方法二位运算 写在最后 Tag
【递归/DFS】【伪回文】【二叉树】【2023-11-25】 题目来源
1457. 二叉树中的伪回文路径 题目解读
伪回文路径指的是路径中的节点值经过重新排序之后可以形成回文数的路径。现在需要返回二叉树中所有从根节点到叶子节点的路径中伪回文路径的数目。 解题思路
伪回文的判断
首先来看一下伪回文路径的判断核心是对于路径节点值的是否具有伪回文性即将这些节点重新排列之后是否可以构成回文数。比如某条路径上的节点值依次为 2 1 1 经过重新排列之后可以形成 1 2 1 这样的回文数这里的定义不是很清楚请继续看下去后面你就会发现其实本题中不需要细究是回文数还是回文串。以下暂且使用回文数来对这样的回文形式进行表达。
回文数分为偶数回文和奇数回文偶数回文指的是回文数中的字符数量是偶数根据回文的特性从左往右与从右往左读到的数都是一致的回文数中每个字符出现的数量都要是偶数。
奇数回文指的是回文数中的字符数量是奇数根据回文的特性从左往右与从右往左读到的数都是一致的回文数中仅有一个字符出现的数量是奇数放置在回文数的中心位置其余字符的出现次数都是偶数。
综上要判断一个路径节点是否是伪回文的只需要统计节点中字符个数为奇数的数量 cnt如果 cnt 0那么就是伪回文的否则不是。
超出空间限制
本题最先想到的就是深搜得到所有可能的数字路径比如示例 1 中的所有路径为 {{233}{231}{211}}然后遍历统计每一个的 vector 中元素的个数仅有一个或者零个元素个数是奇数那么这个 vector就是伪回文的。但是超出空间限制关于空间限制有个疑问 LeetCode空间限制的思考 欢迎讨论。
方法一递归DFS
在深搜的过程中记录这条路径中不同节点出现的次数在遇到叶子节点时统计
如果奇数个节点值的个数 cnt 1则该路径是伪回文的否则不是。
具体地使用一个哈希表 mp 来维护出现的节点的数量设当前节点为 node更新 mp[node-val]
如果当前节点是叶子节点则调用 chek 函数来更新答案 ans否则递归计算左、右子树注意需要回溯的过程即更新 --mp[node-val]。
实现代码
/*** Definition for a binary tree node.* 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 {
private:int ans 0;
public:void dfs(TreeNode* root, unordered_mapint, int mp){if(!root){return;} mp[root-val];if(!root-left !root-right){// 检查当前的路径是否是 伪回文并更新答案check(mp);}dfs(root-left, mp);dfs(root-right, mp);-- mp[root-val];}void check(unordered_mapint, int mp){int cnt 0;for(auto [_, freq] : mp){if(freq 1){ cnt;}}if (cnt 1) { ans;}}int pseudoPalindromicPaths (TreeNode* root) {unordered_mapint, int mp;dfs(root, mp);return ans;}
};复杂度分析
时间复杂度 O ( C × n ) O(C \times n) O(C×n)其中 C C C 是节点中不同元素的数量 n n n 是二叉树中节点数。二叉树中每个元素都会被访问到每次访问的叶子节点判断是否为伪回文路径的时间复杂度为 O ( C ) O(C) O(C)。
空间复杂度 O ( n ) O(n) O(n)深搜深度最深为 O ( n ) O(n) O(n)。
方法二位运算
我们可以使用二进制数来标记路径中的节点出现的数量节点最多有 10 种即从 0 到 9如果某个节点值出现次数为偶数则对应位 1 (node-val) 记为 0如果某个节点值出现次数为奇数则对应位 1 (node-val) 记为 1。我们使用 mask 来表示某条路径中节点出现次数的奇偶数情况比如 100000011 表示节点值 0、1 和 9 出现次数均为奇数。当前节点 node 的 mask 更新为 mask ^ 1 node-val。
如果 mask 中只有一个 1 或者没有 1那么去掉 1 之后mask 就变成 0 了那么判断
KaTeX parse error: Expected EOF, got at position 6: mask̲(mask−1)0
是否成立如果成立则说明 mask 中要么只有一个 1要么全为 0。
实现代码
代码来源 一步步优化从数组到位运算Python/Java/C/Go/JS/Rust。
class Solution {
public:int pseudoPalindromicPaths(TreeNode *root, int mask 0) {if (root nullptr) {return 0;}mask ^ 1 root-val; // 修改 root-val 出现次数的奇偶性if (root-left root-right) { // root 是叶子节点return (mask (mask - 1)) 0;}return pseudoPalindromicPaths(root-left, mask) pseudoPalindromicPaths(root-right, mask);}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( n ) O(n) O(n)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
