企业网站建设word,惠城营销网站制作,v电影主题 wordpress,特效制作软件#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 二叉树 DFS 求解思路 实现代码 运行结果 共勉 题目链接
1457. 二叉树中的伪回文路径
⛲ 题目描述
给你一棵二叉树每个节点的值为 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 求解思路实现代码运行结果 ⚡ 二叉树 DFS 求解思路
考察点1树的深度优先遍历找到从根节点到叶子节点的所有节点。考察点2怎么判断一条路径中的节点是否是一个回文路径呢计数如果一个路径中某一个数字出现的次数是偶数那么忽略如果是奇数至少容忍一次多于一次不可以构成回文路径。考察点3什么是回文序列就是正着读和反着读都一样构成回文序列。具体实现代码如下 实现代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int pseudoPalindromicPaths (TreeNode root) {int[] cntnew int[10];return process(root,cnt);}public int process(TreeNode root,int[] cnt){if(rootnull) return 0;cnt[root.val];int ans0;if(root.leftnullroot.rightnull){int dif0;for(int i0;icnt.length;i){if(cnt[i]%21) dif;}ansdif1?1:0;}else{ansprocess(root.left,cnt)process(root.right,cnt);}cnt[root.val]--;return ans;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
