【LeetCode:1457. 二叉树中的伪回文路径 | 二叉树 + DFS +回文数】

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

🚩 题目链接

• 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. 考察点1：树的深度优先遍历，找到从根节点到叶子节点的所有节点。
2. 考察点2：怎么判断一条路径中的节点是否是一个回文路径呢？计数，如果一个路径中某一个数字出现的次数是偶数，那么忽略，如果是奇数，至少容忍一次，多于一次，不可以构成回文路径。
3. 考察点3：什么是回文序列，就是正着读，和反着读都一样，构成回文序列。
4. 具体实现代码如下：

🥦 实现代码

/*** 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[] cnt=new int[10];return process(root,cnt);}public int process(TreeNode root,int[] cnt){if(root==null) return 0;cnt[root.val]++;int ans=0;if(root.left==null&&root.right==null){int dif=0;for(int i=0;i<cnt.length;i++){if(cnt[i]%2==1) dif++;}ans=dif<=1?1:0;}else{ans=process(root.left,cnt)+process(root.right,cnt);}cnt[root.val]--;return ans;}
}

🥦 运行结果

---

💬 共勉

最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！