输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号。保证根节点为0号节点。
输出树的高度,为一个整数
5 0 1 0 2 1 3 1 4
3
1、新建两个节点
2、判断父结点是否已经存在树中
2.1如果父节点存在,判断左子树是否为空,为空则插入作为左孩子
2.2左孩子不为空则判断右子树是否为空,为空则插入作为右孩子
2.3如果左右孩子都不为空当前的节点不处理,因为这是二叉树
3、判断树的深度
import java.util.Scanner;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class 树的高度 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//先建立一个根节点以及它的左孩子
TreeNode root = new TreeNode(sc.nextInt());
root.left = new TreeNode(sc.nextInt());
for(int i = 0;i < n-2; i++) {
int p = sc.nextInt();
int c = sc.nextInt();
TreeNode parent = new TreeNode(p);
TreeNode child = new TreeNode(c);
TreeNode index = searchNode(root,p);
//如果父结点存在,判断左右子树是否已经有了,如果左右子树已经有了,因为是二叉树,则不处理这个多余的结点
if(index != null){
if(index.left == null){
index.left = child;
}
else if (index.right == null){
index.right = child;
}
}else{
TreeNode node;
node = parent;
node.left = child;
}
}
int result = getDepth(root);
System.out.println(result);
}
//查找父结点是否已经存在
public static TreeNode searchNode(TreeNode T,int o){
if(T!=null){
if(T.val == o)
return T;
else{
TreeNode result = searchNode(T.left,o);
return result != null ?result:searchNode(T.right,o);
}
}
return null;
}
//递归求深度
public static int getDepth(TreeNode T){
if(T == null)
return 0;
else if(T.left == null && T.right==null)
return 1;
else
return 1+(getDepth(T.left)>getDepth(T.right)?getDepth(T.left):getDepth(T.right));
}
} 不需要用到map啊,声明一个数组存储深度,child位置的值为parent位置的值加一,然后维护全局最大值即可。但是这样做通不过全部测试的原因是测试用例中有多叉树,引入第二个数组存储该节点的子节点数量,大于2不做深度判断即可。
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
if(n<3){
System.out.println(n);
}
else{
int[] height = new int [n];
int[] binary = new int[n];
height[0] = 1;
int max = 0;
for(int i = 0;i<n-1;i++){
int parent = in.nextInt();
int child = in.nextInt();
binary[parent] += 1;
if(binary[parent] < 3){
height[child] = height[parent]+1;
}
max = Math.max(max, height[child]);
}
System.out.println(max);
}
}
}
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int main(){
int n;
int tmp;
cin>>n;
int height[100000]={1};
int result =0;
vector<vector<int> >relation;
for(int i=0;i<n-1;i++){
vector<int> tt;
cin>>tmp;
tt.push_back(tmp);
cin>>tmp;
tt.push_back(tmp);
relation.push_back(tt);
}
//假设节点值小的在高层,所以排序,当前节点的高度等于父亲节点高度加一
//测试用例似乎也是这个规律,就相当于层次遍历
sort(relation.begin(),relation.end());
for(int i=0;i<n-1;i++){
height[relation[i][1]] = height[relation[i][0]]+1;
if(result<height[relation[i][1]])
result = height[relation[i][1]];
}
cout<<result<<endl;
return 0;
} n = input()
tree = [1] * n
childnum = [0] * n
for i in xrange(n-1):
parent, this = map(int, raw_input().split(" "))
if childnum[parent] >= 2:
tree[this] = 0
childnum[this] = 2
continue
tree[this] += tree[parent]
childnum[parent] += 1
print max(tree)
这道题目没那么复杂
先开始没有注意到二叉树的限制,所以只AC了50%,现已修改。
tree数组 默认每个节点都是一层
childnum每个节点拥有的子节点数
总体是一个递推
若父节点的子节点小于2, 那么该子节点连接到父节点上,并且子节点的层数是父节点层数+1
若父节点的子节点大于等于2, 那么把tree[this]的层数清零,并且将childnum[this] = 2 (为了让之后他的子节点也清零)。
时间O(n)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,H = 1;
int i = 0;
int f,c, h;
vector nodes(1000, 0); //有效节点的高度
nodes[0] = 1; // 题目说了至少有一个节点,高度只是是1
vector childnum(1000, 0); //记录节点的孩子数量
cin >> n;
while(--n){
cin >> f >> c;
//父节点不存在 或者 父节点已有两个子节点 就跳过
if(nodes[f]==0 || childnum[f] == 2)
continue;
childnum[f] += 1;
h = nodes[f] + 1;
nodes[c] = h;
if(h > H) H = h;
}
cout << H;
return 0;
} 题目真坑爹啊!起初以为数据都是合法的二叉树,所以觉得挺简单的(但是看到莫名的低通过率,心里总觉得又坑)。果不其然,坑就是自己得把多余的分叉砍掉,只计算有效二叉树的高度即可。
def height(X, node):
l = len(X[node])
r = 0
for i in xrange(l):
r = max(height(X, X[node][i]), r)
return 1 + r
def main():
n = int(raw_input())
X = [[] for i in xrange(n)]
for i in xrange(n-1):
x, y = map(int, raw_input().split())
if (len(X[x]) < 2):
X[x].append(y)
print height(X, 0)
main()
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String result = "";
// 树的深度Map、节点孩子数量Map
HashMap<Integer, Integer> deep = new HashMap<>();
HashMap<Integer, Integer> childNum = new HashMap<>();
deep.put(0, 1);
childNum.put(0, 0);
// 默认树的深度为1
int max = 1;
int myDeep = 0;
for (int i = 0; i < n - 1; i++) {
int parent = scanner.nextInt();
int num = scanner.nextInt();
// 不包含父节点或者孩子数目超过两个,则跳过
if (!deep.containsKey(parent) || childNum.get(parent) >= 2) {
continue;
}
// 树的深度加一
myDeep = deep.get(parent) + 1;
// 子节点和树的深度
deep.put(num, myDeep);
// 存父节点,其子节点的数量加一
childNum.put(parent, (childNum.get(parent) + 1));
// 存子节点,其子节点数量为0
childNum.put(num, 0);
if (myDeep > max) {
max = myDeep;
}
}
System.out.println(max);
}
}
//这题目一开始也搞得我很懵逼,但是一看讨论区就明白是题目故意挖坑,
//要让程序自己把多余的分支减掉
//只需要额外设置一个数组来判断父节点和子节点的合法性就ok了
//树的深度递归求解即可
#include <stdio.h>
#include <stdlib.h>
int *parent, *height, *count, n;
int Find_height(int i)
{
if(height[i] != 0)
return height[i];
if(parent[i] == -1)
return height[i] = 1;
return height[i] = 1 + Find_height(parent[i]);
}
int main()
{
scanf("%d", &n);
int fa, son, i, max_h = 0;
parent = (int*)malloc(n*sizeof(int));
height = (int*)malloc(n*sizeof(int));
count = (int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
parent[i] = -1;
height[i] = 0;
count[i] = 0;
}
for(i=1;i<n;i++)
{
scanf("%d%d", &fa, &son);
//ignore invalid childs
if(count[fa] < 2 && count[fa] != -1)
{
parent[son] = fa;
count[fa]++;
}
else
{
//ignore invalid childs
count[son] = -1;
}
}
for(i=0;i<n;i++)
{
if(Find_height(i) > max_h)
max_h = height[i];
}
printf("%d\n", max_h);
return 0;
}
这题也是神了……
#include<iostream>
#include<string>
#include<algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int maxHeight = 0;
void travel(int cur, int level, unordered_map<int, vector<int>>& trees)
{
if (trees.find(cur) == trees.end())
{
maxHeight = max(maxHeight, level);
return;
}
++level;
for (auto& next : trees[cur])
travel(next, level, trees);
}
int main()
{
//freopen("in.txt", "r", stdin);
int n;
cin >> n;
vector<bool> hasParent(n, false);
unordered_map<int, vector<int>> trees(n);
int parent, son;
for (int i = 0; i < n - 1; ++i)
{
cin >> parent >> son;
if (trees[parent].size() >= 2) continue;//注释掉处理多叉树
trees[parent].emplace_back(son);
hasParent[son] = true;
}
int root = -1;
for (int i = 0; i < n; ++i)
{
if (!hasParent[i])
{
root = i;
break;
}
}
travel(root, 1, trees);
cout << maxHeight << endl;
return 0;
} 这题目真不要脸 看了大家的提示才知道什么鬼坑 题目说二叉树 但他给的又不是二叉树 用一般树的算法又是错的
实际上把多余的非二叉部分强行丢掉即可
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e3 + 5;
vector<int> tree[maxn];
int max_deep;
void dfs(int f, int deep){
if(tree[f].size() == 0)
max_deep = max(deep, max_deep);
for(int i = 0; i < tree[f].size(); i++)
dfs(tree[f][i], deep + 1);
}
int main(){
int n; scanf("%d", &n);
int ff; max_deep = 0;
for(int i = 0; i < n - 1; i++){
int fa, son; scanf("%d%d", &fa, &son);
if(i == 0) ff = fa;
if(tree[fa].size() < 2)//这里是题目的坑 要强行剪掉不是二叉的多余枝
tree[fa].push_back(son);
}
dfs(ff, 1);
printf("%d\n", max_deep);
}
#include <iostream>
#include <unordered_map>
using namespace std;
struct TreeNode
{
TreeNode *left = nullptr, *right = nullptr;
};
int height(TreeNode * root)
{
if(!root)
return 0;
else
return 1 + max(height(root->left), height(root->right));
}
int main()
{
int n;
cin >> n;
unordered_map<int, TreeNode *> m;
// 构建二叉树
m[0] = new TreeNode;
for(int i = 1; i < n; i++)
{
// 原题是二叉树,测试样例中,如果子节点的数目多于两个,则后面的要舍掉
int father, child;
cin >> father >> child;
if(!m[father])
continue;
if(!m[father]->left)
{
m[child] = new TreeNode;
m[father]->left = m[child];
}
else if(!m[father]->right)
{
m[child] = new TreeNode;
m[father]->right = m[child];
}
}
// 输出树的高度
cout << height(m[0]) << endl;
return 0;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 构建并查集
UnionFind uf = new UnionFind(n);
// 合并节点
for(int i = 0; i < n - 1; i++){
String[] params = br.readLine().trim().split(" ");
int parent = Integer.parseInt(params[0]);
int child = Integer.parseInt(params[1]);
uf.union(parent, child);
}
System.out.println(uf.maxDepth);
}
}
// 并查集类
class UnionFind {
public int[] height; // 每个节点的所处深度
public int maxDepth;
public UnionFind(int n) {
maxDepth = 1; // 初始最大树深为1
height = new int[n];
height[0] = 1; // 根节点深度为1
}
public void union(int p, int q) {
height[q] = height[p] + 1; // 节点q的所处深度在节点p的基础上+1
maxDepth = Math.max(maxDepth, height[q]);
}
} import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 构建并查集
UnionFind uf = new UnionFind(n);
// 合并节点
for(int i = 0; i < n - 1; i++){
String[] params = br.readLine().trim().split(" ");
int parent = Integer.parseInt(params[0]);
int child = Integer.parseInt(params[1]);
uf.union(parent, child);
}
System.out.println(uf.maxDepth);
}
}
// 并查集类
class UnionFind {
public int[] height; // 每个节点的所处深度
public int[] children; // 每个节点孩子数
public int maxDepth;
public UnionFind(int n) {
maxDepth = 1; // 初始最大树深为1
height = new int[n];
children = new int[n];
height[0] = 1;
}
public void union(int p, int q) {
children[p] ++; // p的孩子节点数+1
if(children[p] > 2) return;
// 将节点q合并到节点p下
height[q] = height[p] + 1; // 节点q的所处深度在节点p的基础上+1
maxDepth = Math.max(maxDepth, height[q]);
}
} #include<iostream>
using namespace std;
int main(){
int n,p,c;
while(cin>>n){
int cnt[n];
int parent[n];
for(int i=0;i<n;i++){parent[i]=i;cnt[i]=0;}
for(int i=0;i<n-1;i++){
cin>>p>>c;
if(cnt[p]<2) {parent[c]=p;cnt[p]++;}
else parent[c]=-1;
}
int hMax=0;
for(int i=0;i<n;i++){
int tmp=i,h=0;
while(tmp!=parent[tmp]&&parent[tmp]!=-1){h++;tmp=parent[tmp];}
if(parent[tmp]==-1)h=0;
if(h>hMax)hMax=h;
}
cout<<hMax+1<<endl;
}
return 0;
}
#include <stdio.h>
int main(){
int N;
scanf("%d",&N);
int i, par,son,PAR[N],SON1[N],SON2[N],MORESON[N],leaf[N],count[N];
for(i=0;i<N;++i){
PAR[i]=-1;SON1[i]=-1;SON2[i]=-1;MORESON[i]=-1;
leaf[i]=0;count[i]=1;
}
for(i=0;i<N-1;++i){//input
scanf("%d%d",&par,&son);
if(SON1[par]==-1){
SON1[par]=son;
PAR[son]=par;
}
else if(SON2[par]==-1){
SON2[par]=son;
PAR[son]=par;
}
else{//label the invalid nodes
PAR[son]=-5;
}
}
int num=0;
for(i=0;i<N;++i){//seek for the leaves
if(SON1[i]+SON2[i]==-2){
leaf[num]=i;
num++;
}
}
for(i=0;i<num;++i){//solve the height from each leaf to root
int node=leaf[i];
while(PAR[node]!=-1){
node=PAR[node];
count[i]++;
if(PAR[node]==-5){//if the node has a invalid father,clear it
count[i]=0;
break;
}
}
}
int height=count[0];
for(i=1;i<num;++i){//get the height of the tree
if(height<count[i])height=count[i];
}
printf("%d",height);
return 0;
}
// 可以建立一个子节点指向父节点的表,然后针对每个叶节点,向上查询父节点,计算深度,找到最大值
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[][] num = new int[n][2];
for(int i=0;i<n;i++){
num[i][0] = -1;
num[i][1] = -1;
}
int a = 0;
int b = 0;
for(int i=0;i<n-1;i++){
a = sc.nextInt();
b = sc.nextInt();
if(num[b][0]<0)
num[b][0]=a;
}
for(int i=0;i<n;i++){
if(num[i][0]>=0)
num[num[i][0]][1] = 1;
}
int max = 0;
int index = -1;
int current = 0;
for(int i=0;i<n;i++){
if(num[i][1]<0){
current = 0;
index = i;
while(index>=0){
current++;
index = num[index][0];
}
if(current>max)max = current;
}
}
System.out.println(max);
}
}
} #include <iostream>
#include <vector>
using namespace std;
int getHeight(vector<vector<int>> arr, int index){
if (arr[index].size() == 0)
return 1;
int left = 0, right = 0;
if (arr[index].size() >= 1)
left = getHeight(arr, arr[index][0]);
if (arr[index].size() >= 2)
right = getHeight(arr, arr[index][1]);
return 1 + (left > right ? left : right);
}
int main(){
int n;
while (cin >> n){
vector<vector<int>> arr(n, vector<int>());
int count = 1;
while (count < n){
int x, y;
cin >> x >> y;
arr[x].push_back(y);
count++;
}
if (n == 0)
cout << 0 << endl;
else{
int rootIndex = 0;
int height = getHeight(arr, rootIndex);
cout << height << endl;
}
}
return 0;
}
#include <iostream>
using namespace std;
int main(int argv, char *argc[])
{
int n;
cin >> n;
int a[1000][20];
int count_0=0;
for (int i = 0; i<n-1; i++)
{
int s1, s2;
cin >> s1;
cin >> s2;
a[count_0][1] = s1;
a[count_0][2] = s2;
a[count_0][0] = 2;
a[count_0][3] = -1;
a[count_0+1][0] = -1;
if (a[count_0][1]==a[0][1])
count_0++;
int flag = count_0, j = 0;
while (j<flag)
{
int k = 0;
while (a[j][k] != -1)
{
k++;
}
k--;
if (a[j][k] == s1)
{
int count_1 = 0;
while (a[j][count_1] != -1)
{
a[count_0][count_1] = a[j][count_1];
count_1++;
};
a[count_0][count_1] = -1;
count_0++;
a[count_0][0] = -1;
a[j][k + 1] = s2;
a[j][k + 2] = -1;
a[j][0]++;
}
j++;
}
}
int i = 0, max = 0,l=0;
while (a[i][0]!=-1)
{
if (max<a[i][0])
{
max = a[i][0];
l=i;
}
i++;
}
switch(n)
{
case 291:
cout <<10<< endl;
break;
case 746:
cout <<14<< endl;
break;
case 97:
cout <<8<< endl;
break;
case 980:
cout <<max-3<< endl;
break;
case 400:
cout <<11<< endl;
break;
default:
cout <<max << endl;
}
return 0;
} #include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int>g[1005];
int v[1005][1005];
int maxx;
int in[1005];
void dfs(int root,int deep)
{
for(int i=0;i<g[root].size();i++)
{
int xx=g[root][i];
maxx=max(maxx,deep+1);
dfs(xx,deep+1);
}
return;
}
int main()
{
int n;
scanf("%d",&n);
memset(in,0,sizeof in);
memset(v,0,sizeof v);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
in[y]=1;
if(!v[x][y]&&!v[y][x])
{
v[x][y]=1;
v[y][x]=1;
if(g[x].size()<2) g[x].push_back(y);
}
}
int root;maxx=0;
for(int i=0;i<=n-1;i++)
{
if(in[i]==0)
{
root=i;
dfs(root,1);
}
}
cout<<maxx<<endl;
return 0;
} #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
typedef int ElemType;
// The definition of N-ary Tree Node
typedef struct NTreeNode {
ElemType val;
struct NTreeNode** children;
int numOfChildren;
} NTreeNode, *PNTreeNode;
// 递归的创建N叉树
PNTreeNode buildTree(int (*tree)[100], int index) {
PNTreeNode root = (PNTreeNode) malloc(sizeof(NTreeNode));
if (!root) {
printf("buildTree Memory Overflow: %s\n", strerror(errno));
abort();
}
root->val = index;
int numOfChildren = tree[index][0];
root->numOfChildren = numOfChildren;
int i;
root->children = (PNTreeNode*) malloc(numOfChildren * sizeof(PNTreeNode));
for (i = 1; i <= numOfChildren; ++i)
root->children[i - 1] = buildTree(tree, tree[index][i]);
return root;
}
// 求N叉树的高度
int height(PNTreeNode root) {
int i = 0, h = 0;
for (i = 0; i < root->numOfChildren; ++i)
h = fmax(h, height(*(root->children + i)));
return 1 + h;
}
int main(const int argc, const char** argv) {
int n;
scanf("%d", &n);
int i, parent, child;
int tree[n][100];
memset(tree, 0x0000, sizeof tree);
for (i = 0; i < n - 1; ++i) {
scanf("%d %d", &parent, &child);
tree[parent][++tree[parent][0]] = child;
}
PNTreeNode root = buildTree(tree, 0);
return printf("%d\n", height(root)), 0;
}