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

柔光的暖阳◎ 2022-12-24 04:53 35阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

因为值在1 - 9 之间

1.  两个相同的值异或为0

2^2^3^3 = 10 ^ 10 ^ 100 ^ 100 = 0

1.  回文有两种情况：

2^2^3^3 = 10 ^ 10 ^ 100 ^ 100 = 0   // 回文
    2^2^3^3^4 = 10 ^ 10 ^ 100 ^ 100 ^ 4= 4 = 100 // 回文
    2^2^3^3^4 = 10 ^ 10 ^ 100 ^ 100 ^ 3^ 4= 3^ 4 = 100 ^ 1000 = 1100 ---> // 不是回文，两个1
    2^2^3^3^4^5 = 10 ^ 10 ^ 100 ^ 100 ^ 3^ 4^5= 3^ 4 = 100 ^ 1000 ^ 10000= 11100  // 不是回文

只需要判断最后的结果是不是0 或者只有一个1即可

1.  假设最后的值是n， 如果当前值的二进制只有一个1，我们可以通过`n & (n - 1)`来消去最后一个1

3 & 2 = 100 & 10 = 0

/**
     * 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 {
        
    
    private int count = 0;
        public int pseudoPalindromicPaths (TreeNode root) {
        
            if (root == null){
        
                return 0;
            }
            
            helper(root, 0);
            return count;
        }
        
        private void helper(TreeNode root, int num){
        
            int val = num ^ (1 << root.val);
            if (root.left == null && root.right == null){
        
                if (val == 0 || (val & (val - 1)) == 0){
        
                    count++;
                }
                return ;
            }
            
            if (root.left != null){
        
                helper(root.left, val);
            }
            if (root.right != null){
        
                helper(root.right, val);
            }
        }
    
       
    }

![在这里插入图片描述][20201126193956828.png_pic_center]

[1457.]: https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9c90bdfe0f634e2d8763dbb087b6fa4c.png
[20201126193956828.png_pic_center]: https://img-blog.csdnimg.cn/20201126193956828.png#pic_center