LEETCODE 1457. Pseudo-Palindromic Paths in a Binary Tree 解题思路分析

二叉树中的伪回文路径

给你一棵二叉树,每个节点的值为 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 到 10^5 之间。
  • 节点值在 1 到 9 之间。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1457

解题思路分析:

老规矩,二叉树应考虑使用dfs来解题。另外判断二叉树路径是否为伪回文路径的问题应该是在leetcode中首次出现(也许是我还没刷到过),这个问题难度并不大,我们只要统计出路径中每种字符出现的个数,然后在路径尾部来判断“落单”字符的个数,如果个数小于等于1代表该路径为伪回文路径,反之则不是。这里简单来解释一下,对于一个回文,就像洋葱一般,右外层到内层都是首尾相同的,因此每种出现过的字符数量一定是偶数个。只存在一个特例即是长度为奇数的回文正中间的那个字符,只有它存在单独出现的可能。

实现代码:

int res=0;
public int pseudoPalindromicPaths (TreeNode root) {
    help(root,new int[10]);
    return res;
}

void help(TreeNode root, int[] count){
    count[root.val]++;
    if(root.left!=null) help(root.left, count);
    if(root.right!=null) help(root.right, count);
    if(root.left==null&&root.right==null){
        int c=0;
        for(int i=1;i<=9;i++){
            c+=(count[i]%2);
            if(c>1) break;
        }
        if(c<=1) res++;
    }
    count[root.val]--;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 97.33% of Java online submissions for Pseudo-Palindromic Paths in a Binary Tree.

Memory Usage: 57.4 MB, less than 100.00% of Java online submissions for Pseudo-Palindromic Paths in a Binary Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1457-pseudo-palindromic-paths-in-a-binary-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。