【Leetcode合集】1457. 二叉树中的伪回文路径

2023-11-27 07:01

本文主要是介绍【Leetcode合集】1457. 二叉树中的伪回文路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1457. 二叉树中的伪回文路径

1457. 二叉树中的伪回文路径

代码仓库地址: https://github.com/slience-me/Leetcode

个人博客 :https://slienceme.xyz

  • 给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。

    请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

示例 1:

在这里插入图片描述

输入:root = [2,3,1,3,1,null,1]
输出:2 
解释:上图为给定的二叉树。总共有 3 条从根到叶子的路径:红色路径 [2,3,3] ,绿色路径 [2,1,1] 和路径 [2,3,1] 。在这些路径中,只有红色和绿色的路径是伪回文路径,因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ,绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。

示例 2:

在这里插入图片描述

输入:root = [2,1,1,1,3,null,null,null,null,null,1]
输出:1 
解释:上图为给定二叉树。总共有 3 条从根到叶子的路径:绿色路径 [2,1,1] ,路径 [2,1,3,1] 和路径 [2,1] 。这些路径中只有绿色路径是伪回文路径,因为 [2,1,1] 存在回文排列 [1,2,1] 。

示例 3:

输入:root = [9]
输出:1

提示:

  • 给定二叉树的节点数目在范围 [1, 105]内
  • 1 <= Node.val <= 9

方案1:递归方法

伪回文数:N个对数+1个单数

采用vector给1-9的数字计数,定义变量count

为叶子结点时,判断计数count的各个数字的计数是否满足条件

然后递归

/*** 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 {
public:int countPseudoPalindromic(TreeNode *root, vector<int> &count) {// 该结点为空则返回0if (root == nullptr) return 0;// 值计数+1count[root->val]++;// 判定叶子结点if (root->left == nullptr && root->right == nullptr) {// 到达叶子节点时检查路径的伪回文性质int oddCount = 0; //记录伪路径数for (int i = 1; i <= 9; ++i) {if (count[i] % 2 != 0) { //存在奇数  233->323(1+0) yes 1232(1+0+1) nooddCount++;}}count[root->val]--;//返还个数return oddCount <= 1 ? 1 : 0;//N个对数+1个单数}int leftCount = countPseudoPalindromic(root->left, count);int rightCount = countPseudoPalindromic(root->right, count);count[root->val]--;return leftCount + rightCount;}int pseudoPalindromicPaths(TreeNode *root) {vector<int> count(10, 0); // 存储节点值的出现次数return countPseudoPalindromic(root, count);}
};

执行用时分布 268ms 击败93.50%使用 C++ 的用户

消耗内存分布177.11MB 击败32.00%使用 C++ 的用户

方案2:初次优化

代码优化有限,vector变为原生数组,基本没有太大效果

/*** 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 {
public:int countPseudoPalindromic(TreeNode *root, int count[]) {// 该结点为空则返回0if (root == nullptr) return 0;// 值计数+1count[root->val]++;// 判定叶子结点if (root->left == nullptr && root->right == nullptr) {// 到达叶子节点时检查路径的伪回文性质int oddCount = 0; //记录伪路径数for (int i = 1; i <= 9; ++i) {if (count[i] % 2 != 0) { //存在奇数  233->323(1+0) yes 1232(1+0+1) nooddCount++;}}count[root->val]--;//返还个数return oddCount <= 1 ? 1 : 0;//N个对数+1个单数}int leftCount = countPseudoPalindromic(root->left, count);int rightCount = countPseudoPalindromic(root->right, count);count[root->val]--;return leftCount + rightCount;}int pseudoPalindromicPaths(TreeNode *root) {int count[10]= {0};return countPseudoPalindromic(root, count);}
};

执行用时分布 260ms 击败98%使用 C++ 的用户

消耗内存分布176.33MB 击败39.50%使用 C++ 的用户

方案3:代码简化

效率没有提高

/*** 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 {
public:void judgement() {int oddCount = 0; //记录伪路径数for (int i = 1; i <= 9; ++i) { // N个对数+1个单数if (counts[i] % 2 != 0) { //==1 存在奇数且是3  233->323(1+0) yes 1232(1+0+1) nooddCount++; //记录单个数的个数}}res+= (oddCount <= 1) ? 1 : 0;//N个对数+1个单数}void countPseudoPalindromic(TreeNode *root) {// 空结点情况if (root == nullptr) return;// 叶子结点情况if (root->left == nullptr && root->right == nullptr) {counts[root->val]++; // 值计数+1judgement();counts[root->val]--;//返还个数return;}// 普通结点情况counts[root->val]++;countPseudoPalindromic(root->left);countPseudoPalindromic(root->right);counts[root->val]--;}int pseudoPalindromicPaths(TreeNode *root) {counts.resize(10);//修改大小countPseudoPalindromic(root);return res;}private:vector<int> counts;int res=0;
};

执行用时分布 296ms 击败56.50%使用 C++ 的用户

消耗内存分布175.59MB 击败56.00%使用 C++ 的用户

这篇关于【Leetcode合集】1457. 二叉树中的伪回文路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/427233

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

EasyPlayer.js网页H5 Web js播放器能力合集

最近遇到一个需求,要求做一款播放器,发现能力上跟EasyPlayer.js基本一致,满足要求: 需求 功性能 分类 需求描述 功能 预览 分屏模式 单分屏(单屏/全屏) 多分屏(2*2) 多分屏(3*3) 多分屏(4*4) 播放控制 播放(单个或全部) 暂停(暂停时展示最后一帧画面) 停止(单个或全部) 声音控制(开关/音量调节) 主辅码流切换 辅助功能 屏

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &