# LeetCode 1803. Count Pairs With XOR in a Range (二叉树)

```   struct Node
{
int value;
int left;
int right;
int num;
int pos;
}tree[200005];

class Solution {
public:

int hight;
int lower;
int fun(int root, int number, int h, int l, int pos)
{
if(pos==-1 )
return tree[root].num;
int b = number & (1 << pos);
if(b>0) b=1;
int ans = 0;

int l1 = lower & (1 << pos);
int h1 = hight & (1 << pos);
if(l1>0) l1 =1;
if(h1>0) h1 =1;
if (h == 1 && l == 1)
{
ans = tree[root].num;
}
else if (h == 1 && l == 0)
{
if (b == 1 && l1 ==1)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
else if (b == 1 && l1 == 0)
{
ans = fun(tree[root].left, number, h, 1, pos - 1) + fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && l1 == 1)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && l1 == 0)
{
ans = fun(tree[root].left, number, h, l, pos - 1) + fun(tree[root].right, number, h, 1, pos - 1);
}
}
else if (h == 0 && l == 1)
{
if (b == 1 && h1 == 1)
{
ans = fun(tree[root].left, number, h, l, pos - 1) + fun(tree[root].right, number, 1, l, pos - 1);
}
else if (b == 1 && h1 == 0)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && h1 == 1)
{
ans = fun(tree[root].left, number, 1, l, pos - 1) + fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && h1 == 0)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
}
else if (h == 0 && l == 0)
{
if (h1 == l1 && h1 == 0)
{
if (b == 1)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
}
else if (h1 == l1 && h1 == 1)
{
if (b == 1)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
else if (b == 0)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
}
else if (h1 == 1 && l1 == 0)
{

if (b == 1)
{
ans = fun(tree[root].left, number, h, 1, pos - 1) + fun(tree[root].right, number, 1, l, pos - 1);
}
else if (b == 0)
{
ans = fun(tree[root].left, number, 1, l, pos - 1) + fun(tree[root].right, number, h, 1, pos - 1);
}
}

}

return ans;
}
int pos2;
void init(int root, int p)
{
if (p == 16)
return;
tree[root].left = ++pos2;
tree[root].right = ++pos2;
tree[root].num=0;
init(tree[root].left, p + 1);
init(tree[root].right, p + 1);
}

void init2(int root,int num, int p)
{
tree[root].num++;
if(p==-1)
return;
int b = num &(1<<p);
if(b>0)
{

init2(tree[root].right,num,p-1);
}
else
{

init2(tree[root].left,num,p-1);
}
}
int countPairs(vector<int>& nums, int low, int high)
{
pos2 = 0;
init(0, 0);
hight = high;
lower = low;
int res = 0;
for (int i = 0; i < nums.size(); i++)
{
res += fun(0, nums[i], 0, 0, 14);
init2(0,nums[i],14);
}

return res;
}
};```

0 条评论

• ### LeetCode Weekly Contest 42解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### C++版 - 剑指Offer 面试题36：数组中的逆序对及其变形(Leetcode 315. Count of Smaller Numbers After Self)题解

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

• ### 【LeetCode】数据结构与算法 最短路径

其实，8-10遍高频效果是最好的，这基本就是到另一个境界了。当然，大家没有那么多时间，3-5遍也可以去面试了。

• ### LeetCode Weekly Contest 35解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 二叉树问题（二）-LeetCode 965、563、993、958、919（树深度，层次遍历）

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时，才返回 true；否则返回 false。

• ### LeetCode笔记：Weekly Contest 241 比赛记录

如上一个博客所述，这周的比赛其实因为一些琐事没能参加，只是赛后做了一下比赛的题目，这里就大致记录一下吧。

• ### 剑指offer【50~59】

排序数组，很明显二分查找，找到第一个 >= k 的元素索引以及第一个 > k 的元素索引，两者相减即为答案，即 lowerBound - upperBound。...

• ### 【leetcode刷题】T136-二叉搜索树中的众数

https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

• ### 第二轮 Python 刷题笔记一：数组

经过四十多天缓慢的刷题，现在进度大概是刷了八十多道 LeetCode 题，最近也在吸取过来人的经验，仍然需要对刷题计划进行调整。

• ### LeetCode刷题记录(easy难度1-20题)

leetcode刷题记录 本文记录一下leetcode刷题记录，记录一下自己的解法和心得。

• ### 【leetcode刷题】T146-二叉树的层平均值

https://leetcode-cn.com/problems/average-of-levels-in-binary-tree

• ### Python3刷题系列（四）

https://leetcode.com/problems/happy-number/

• ### LeetCode 297：二叉树的序列化与反序列化 Serialize and Deserialize Binary Tree

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重...

• ### LeetCode 230. 二叉搜索树中第K小的元素（中序遍历）

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

• ### Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质： ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆，费波纳茨堆等等。如果一棵二叉树最下层上的...

• ### Js算法与数据结构拾萃（4）：二叉树

因此只要答对这道题，你就可以超越世界级大牛，问鼎码林之巅（逃） 导读： •二叉树知识重点•二叉树深度不一，因此天生适用递归，因此可用递归处理•判断两树相等•翻转...

• ### ​LeetCode刷题实战132：分割回文串 II

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...