poj 2309BST解题报告

这道题是给出了这样的结构的一棵树，要找的是给一个根的值，找出这个树节点的最大值和最小值。我们可以很容易观察到每个节点所处的高度是和其包含的2的个数所决定的，而且其左儿子的递减速度为4-2-1，右儿子的递增素速度为4-2-1，那么我们只要将其二进制的最后一个1挪到最后一位，就可得到其最小值，将其二进制的最后一个1后面所有的0都置一就可以得到最大值

View Code

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int t;
 5     scanf("%d",&t);
 6     int n;
 7     int min,max;
 8     int i;
 9     while(t--)
10     {
11         scanf("%d",&n);
12         i=n&-n;
13         max=n|(i-1);
14         min=n-(i-1);
15         printf("%d %d\n",min,max);
16     }
17     return 0;
18 }