个人网站可备案,天津网站优化哪家好,wordpress手机端侧面小工具,h5视频网站模板题目#xff1a;
1457. 二叉树中的伪回文路径
给你一棵二叉树#xff0c;每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的#xff0c;当它满足#xff1a;路径经过的所有节点值的排列中#xff0c;存在一个回文序列。
请你返回从根到叶子节点的所有路…题目
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
解答 代码
/*** 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[] counternew int[10];return dfs(root,counter);}public int dfs(TreeNode root,int[] counter){if(rootnull){return 0;}counter[root.val];int res0;if(root.leftnullroot.rightnull){if(isPseudoPalindrome(counter)){res1;}}else{resdfs(root.left,counter)dfs(root.right,counter);}counter[root.val]--;return res;}public boolean isPseudoPalindrome(int[] counter){int odd0;for(int value:counter){if(value%21){odd;}}return odd1;}
}
结果
