complete binary tree problem

An original problem description

BST - POJ 2309 - Virtual Judgehttps://vjudge.net/problem/POJ-2309

Two Inputs and Outputs

1 input

Line 1 contains an integer N representing the number of queries.In the next N lines, each line contains a number representing the subtree with root X.

2 output

N rows, where row i contains the answer to query i.

Three input and output samples

1 Input example

2

8

10

2 Sample output

1 15

9 11

Four Analysis

The rules of this problem can be followed. If n is an odd number, it must be a leaf node, and the maximum and minimum numbers are itself.Otherwise, find the level where n is located (the reciprocal level, the bottom layer is 0), and its level is the position i of the first 1 from the low bit in the binary representation of n (the last non-zero bit), such as the two of 6The hierarchy is 110, the position of the first 1 from the low position is 1, so 6 is in the first layer; the binary of 12 is 1100, and the position of the first 1 from the low position is 2, so 12 is in the second layer, as followsas shown in the figure.

The value of

i is the number of layers. It can be obtained that the left and right subtrees of n each have k = 2^i-1 nodes, then the minimum number is n-k, and the maximum number is n+k, then how to find 2^i??

Actually, if you want to get the last non-zero bit, you only need to invert the original number and then add 1. At this time, except for the last non-zero bit, the other bits are opposite to the original number, and the bitwise AND operation is directly performed with the original number.You can get the last non-zero bit.

Five algorithm design

1 Solve for logbit(n)=n&(-n).

2 Let see = lowbit(n)-1, output the minimum number n-k, the maximum number n+k.

Six codes

package poj2309;import java.util.Scanner;public class Poj2309 {static int lowbit(int n) {return n & (-n);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T, n, k;T = scanner.nextInt();while (T--> 0) {n = scanner.nextInt();k = lowbit(n) - 1;System.out.println((n - k) + " " + (n + k));}}}

Seven Tests

Green is input, white is output