规则树

发表于   |   分类于   |  

题目：某规则二叉树的定义是：对于树中任意两个叶结点A、B，他们与根结点的距离分别是d1和d2，|d1-d2|<=1。请写出函数 bool isRuledTree(Node *root)的代码实现。如果该二叉树为规则树，则返回true，否则返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#include<vector>

using namespace std;

struct node
{
	int val;
	node* left;
	node* right;
	node()
	{
		val = 1;
		left = NULL;
		right = NULL;
	}
};
vector<int> s;

void leafDepth(node*root,int depth)
{
	if (root == NULL) return;
	if (root->left == NULL&&root->right == NULL)
	{
		s.push_back(depth);
	}
	if (root->left != NULL)
	{
		leafDepth(root->left, depth + 1);
	}
	if (root->right != NULL)
	{
		leafDepth(root->right, depth + 1);
	}
}

bool isRuledTree(node*root)
{
	if (root == NULL)
		return true;
	leafDepth(root, 0);
	int mi = 0x7fffffff;
	int ma = 0x80000000;
	for (int i = 0; i < s.size(); i++)
	{
		if (mi > s[i]) mi = s[i];
		if (ma < s[i]) ma = s[i];
	}
	int x = mi - ma;
	if (x>1 || x < -1)
		return false;
	else return true;
}

int main()
{
	node *root = new node;
	root->left = new node;
	root->right = new node;
	root->right -> left = new node;
	root->right->left->left = new node;
	bool flag = isRuledTree(root);

	return 0;
}