承接上一篇文章，題目同樣來(lái)自2016微軟探星夏令營(yíng)在線技術(shù)筆試球化。這道題主要考察的是樹(shù)的構(gòu)建與遍歷众旗。
題目：
時(shí)間限制:10000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
描述
Let's draw a picture of full binary tree using ASCII characters. In this picture nodes are represented by '#'. A parent node connects its left child by '/' and its right child by ''.
For the sake of aesthetic, the nodes of the same height must be painted on the same line. And the nodes must be perfectly connected by '/' and ''. Intersections or misplacements are not allowed.
For example, this is the full binary tree of height 2:
#
/ \
# #
This is the full binary tree of height 3:
#
/ \
/ \
# #
/ \ / \
# # # #
This is the full binary tree of height 4:
#
/ \
/ \
/ \
/ \
/ \
# #
/ \ / \
/ \ / \
# # # #
/ \ / \ / \ / \
# # # # # # # #
Now we build a Cartesian coordinate system for the picture. We make the root at the origin (0, 0). The positive direction of x is to the bottom and the positive direction of y is to the right.
The full binary tree of height 2 is illustrated as below.
0
+-----+--------> y
|
0+ #(0,0)
| / \
| # #
|(2,-2) (2,2)
|
v
x
Given the height of the tree and a rectangle area of the picture, your task is to find out the amount of nodes in such area. For example, assuming the height of tree is 2, the left-top corner of the rectangle area is at (0, 0) and the right-bottom corner is at (2, 2), then the area contains 2 nodes (the root and its right child) totally.
輸入
The first line contains two integers N and M.
N is the height of the full binary tree. M is the number of queries. (1 ≤ N≤ 20, 1 ≤ M≤ 100)Each query consists of 4 integers x1, y1, x2 and y2. (x1, y1) is the left-top corner of the area and (x2,y2) is the right-bottom corner of the area.
輸出
For each query output the amount of nodes in the area.
樣例輸入
2 3
0 0 0 0
0 0 2 2
0 -2 2 2
樣例輸出
1
2
3
解釋：
題目描述了一種用ASCII碼繪制的滿二叉樹(shù)夕土，然后將樹(shù)的根設(shè)置在一個(gè)特殊坐標(biāo)軸的原點(diǎn)（0埠戳，0）井誉，坐標(biāo)軸x向下為正向，y向右是正向整胃。樹(shù)的每個(gè)樹(shù)枝與節(jié)點(diǎn)都占用1*1的大小】攀ィ現(xiàn)在需要求在坐標(biāo)軸中任意畫(huà)一個(gè)矩形，里面會(huì)有多少個(gè)樹(shù)的節(jié)點(diǎn)屁使。例如樣例輸入中在岂，對(duì)于（0，0）與（2蛮寂，2）形成的矩形里面蔽午，包含有根節(jié)點(diǎn)和它的右葉子節(jié)點(diǎn)，所以輸出的是2共郭。
分析：
1祠丝、這是是一個(gè)二叉樹(shù)的問(wèn)題，肯定要構(gòu)造樹(shù)結(jié)構(gòu)除嘹，為了簡(jiǎn)單写半，這里就聲明一個(gè)Node的結(jié)構(gòu)體，通過(guò)結(jié)構(gòu)體指針來(lái)構(gòu)建樹(shù)尉咕。代碼如下：
struct Node {
Node *lchild, *rchild;
long px, py;
Node(long _px, long _py)
{
lchild = rchild = NULL;
px = _px;
py = _py;
}
};
px叠蝇，py是節(jié)點(diǎn)的坐標(biāo)，lchild與rchild分別對(duì)應(yīng)左右子節(jié)點(diǎn)年缎。
2悔捶、接下里就是生成樹(shù)，這里輸入就是樹(shù)的高度单芜，我們就根據(jù)高度來(lái)生成滿二叉樹(shù)蜕该。生成的時(shí)候根據(jù)題目規(guī)則，我們需要注意樹(shù)的樹(shù)枝占位情況洲鸠。通過(guò)分析我們可以得出堂淡，高度為1的節(jié)點(diǎn)，它一邊的樹(shù)枝數(shù)量是0扒腕，高度2的為1绢淀，高度3的為2，其它高度的節(jié)點(diǎn)樹(shù)枝數(shù)量是其子節(jié)點(diǎn)數(shù)量的2倍加1瘾腰。這樣我們可以用個(gè)遞歸實(shí)現(xiàn)皆的。代碼如下：
long stickNumWithHeight(int height)
{
if (height == 1) {
return 0;
}
if (height == 2) {
return 1;
}
if (height == 3) {
return 2;
}
return stickNumWithHeight(height - 1) * 2 + 1;
}
void buildTreeWithHeight(Node &node, int height)
{
if (height == 1) {
return;
}
long step = stickNumWithHeight(height) + 1;
node.lchild = new Node(node.px + step, node.py - step);
node.rchild = new Node(node.px + step, node.py + step);
buildTreeWithHeight(*node.lchild, height-1);
buildTreeWithHeight(*node.rchild, height-1);
}
3、樹(shù)生成過(guò)后蹋盆，我們只需要對(duì)每個(gè)矩形遍歷檢測(cè)這棵樹(shù)费薄，就可得到在當(dāng)前矩形中節(jié)點(diǎn)數(shù)量，代碼如下：
int checkNodeInArea(Node &node, int x1, int y1, int x2, int y2)
{
int sum = 0;
if (node.px >= x1 && node.py >= y1 && node.px <= x2 && node.py<= y2) {
sum += 1;
}
if (node.lchild != NULL) {
sum += checkNodeInArea(*node.lchild,x1,y1,x2,y2);
}
if (node.rchild != NULL) {
sum += checkNodeInArea(*node.rchild,x1,y1,x2,y2);
}
return sum;
}
判定結(jié)果：
完整代碼：
//
// main.cpp
// Full Binary Tree Picture
//
// Created by Jiao Liu on 8/5/16.
// Copyright ? 2016 ChangHong. All rights reserved.
//
#include <iostream>
#include <math.h>
using namespace std;
struct Node {
Node *lchild, *rchild;
long px, py;
Node(long _px, long _py)
{
lchild = rchild = NULL;
px = _px;
py = _py;
}
};
long stickNumWithHeight(int height)
{
if (height == 1) {
return 0;
}
if (height == 2) {
return 1;
}
if (height == 3) {
return 2;
}
return stickNumWithHeight(height - 1) * 2 + 1;
}
void buildTreeWithHeight(Node &node, int height)
{
if (height == 1) {
return;
}
long step = stickNumWithHeight(height) + 1;
node.lchild = new Node(node.px + step, node.py - step);
node.rchild = new Node(node.px + step, node.py + step);
buildTreeWithHeight(*node.lchild, height-1);
buildTreeWithHeight(*node.rchild, height-1);
}
int checkNodeInArea(Node &node, int x1, int y1, int x2, int y2)
{
int sum = 0;
if (node.px >= x1 && node.py >= y1 && node.px <= x2 && node.py<= y2) {
sum += 1;
}
if (node.lchild != NULL) {
sum += checkNodeInArea(*node.lchild,x1,y1,x2,y2);
}
if (node.rchild != NULL) {
sum += checkNodeInArea(*node.rchild,x1,y1,x2,y2);
}
return sum;
}
int main(int argc, const char * argv[]) {
int N,M;
scanf("%d %d",&N,&M);
Node *root = new Node(0,0);
buildTreeWithHeight(*root,N);
while (M--) {
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int amout = checkNodeInArea(*root,x1,y1,x2,y2);
cout<<amout<<endl;
}
return 0;
}
