小米编程题，树的高度一直是只通过10%

import java.util.Scanner; class Main{ public static void main(String[] args) { Scanner in= new Scanner(System.in); while(in.hasNext()){ int n = in.nextInt(); int[] tree = new int[n]; for (int i = 0; i < tree.length; i++) { tree[i]=-1; } for(int i =0;i<n-1;i++){ int p = in.nextInt(); int c = in.nextInt(); tree[c] =p; } int max=1; int count =0; for (int i = n-1; i >0; --i) { int cur=i; while(cur!=-1) { cur = tree[cur]; count++; } if(count>max) max =count; count=0; } System.out.println(max); } } } //这个应该是O（n）的做法了吧 AC了

100%AC代码，注意下面我数组设1009和2009都会报错，改成n之后就ac了。。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int n; int height(vector<vector<int> >&kid, int root){ if(root < 0 || root >= n) return 0; if(kid[root].empty()) return 1; int h = 0; for(auto x: kid[root]) h = max(h, height(kid, x)); return h+1; } int main() { int parent, child; cin>>n; vector<int>indegree(n, 0); vector<vector<int> >kid(n, vector<int>()); for(int i=1; i<n; i++){ scanf("%d %d", &parent, &child); indegree[child]++; kid[parent].push_back(child); } int maxH = 0; for(int i = 0; i<n; i++){ if(indegree[i] == 0) maxH = max(maxH, height(kid, i)); } cout<<maxH<<endl; return 0; }

0 不一定是根。。这就是这道题坑的地方，别想当然

用递归，把0当做根AC了

确定根节点是哪个。然后bfs或者dfs

不暴力40%，你10%据我实验是在0，1，2个节点其中一个的测试用例。。。。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[] p = new int[n]; int[] l = new int[n]; int[] r = new int[n]; int root=0; for(int i=0;i<n;i++){ p[i]=-1; l[i]=-1; r[i]=-1; } for(int i=0;i<n-1;i++){ int tmpp = in.nextInt(); int tmpc = in.nextInt(); p[tmpc]=tmpp; if(l[tmpp]==-1)l[tmpp]=tmpc; else r[tmpp]=tmpc; } for(int i=0;i<n;i++){ if(p[i]==-1){ root=i; break; } } System.out.println(result(root,l,r)); } in.close(); } private static int result(int start, int[] l, int[] r){ if(l[start]==-1&&r[start]==-1)return 1; if(l[start]==-1&&r[start]!=-1)return 1+result(r[start],l,r); if(r[start]==-1&&l[start]!=-1)return 1+result(l[start],l,r); else return Math.max(1+result(r[start],l,r), 1+result(l[start],l,r)); } }

70% 为啥？ #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <set> #include <vector> using namespace std; int a[1010][3]; bool flag[1010]; int dfs(int now) {     if (a[now][0] == 0) return 1;     if (a[now][0] == 1) return dfs(a[now][1]) + 1;     if (a[now][0] == 2) return max(dfs(a[now][1]), dfs(a[now][2])) + 1; } int main() {     int n, start;     while(cin >> n) {         for (int i = 0; i < n; i++) {             a[i][0] = 0;             flag[i] = false;         }         for (int i = 0; i < n - 1; i++) {             int x, y;             cin >> x >> y;             a[x][++a[x][0]] = y;         }         for (int i = 0; i < n; i++) {             for (int j = 1; j <= a[i][0]; j++) {                 flag[a[i][j]] = true;             }         }         for (int i = 0; i < n; i++) {             if (!flag[i]) {                 start = i;                 break;             }         }         //cout << start << endl;         cout << dfs(start) << endl;     } return 0; }

需要指向父亲的指针，找到根

确实是大坑。。

import java.util.*; public class Main { private static class TreeNode { int value; ArrayList<TreeNode> sons = new ArrayList<>(); public TreeNode(int value) { this.value = value; } } private static Map<Integer, TreeNode> int2TreeNode = new HashMap<>(); public static void main(String args[]) throws Exception { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { int n = cin.nextInt(); HashSet<Integer> parents = new HashSet<>(); HashSet<Integer> sons = new HashSet<>(); for (int i = 0; i < n - 1; i++) { int parent = cin.nextInt(); int son = cin.nextInt(); if (!int2TreeNode.containsKey(parent)) { int2TreeNode.put(parent, new TreeNode(parent)); } if (!int2TreeNode.containsKey(son)) { int2TreeNode.put(son, new TreeNode(son)); } int2TreeNode.get(parent).sons.add(int2TreeNode.get(son)); parents.add(parent); sons.add(son); } parents.removeAll(sons); int root = 0; for (Integer item : parents) { root = item; } System.out.println(dfs(root)); } } private static int dfs(int root) { TreeNode rootNode = int2TreeNode.get(root); if (rootNode == null || rootNode.sons.size() == 0) return 1; else { int maxx = 0; for (int i = 0, len = rootNode.sons.size(); i < len; i++) { int nextRoot = rootNode.sons.get(i).value; if (nextRoot != root) { maxx = Math.max(maxx, dfs(nextRoot)); } } return maxx + 1; } } }

题目讲的不明不白的，看起来好像就是0是根。。。原来不是，我说呢

import java.util.*; public class Main { private static class TreeNode { int value; ArrayList<TreeNode> sons = new ArrayList<>(); public TreeNode(int value) { this.value = value; } } private static Map<Integer, TreeNode> int2TreeNode = new HashMap<>(); public static void main(String args[]) throws Exception { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { int n = cin.nextInt(); HashSet<Integer> parents = new HashSet<>(); HashSet<Integer> sons = new HashSet<>(); for (int i = 0; i < n - 1; i++) { int parent = cin.nextInt(); int son = cin.nextInt(); if (!int2TreeNode.containsKey(parent)) { int2TreeNode.put(parent, new TreeNode(parent)); } if (!int2TreeNode.containsKey(son)) { int2TreeNode.put(son, new TreeNode(son)); } int2TreeNode.get(parent).sons.add(int2TreeNode.get(son)); parents.add(parent); sons.add(son); } parents.removeAll(sons); int root = 0; for (Integer item : parents) { root = item; } System.out.println(dfs(root)); } } private static int dfs(int root) { TreeNode rootNode = int2TreeNode.get(root); if (rootNode == null || rootNode.sons.size() == 0) return 1; else { int maxx = 0; for (int i = 0, len = rootNode.sons.size(); i < len; i++) { int nextRoot = rootNode.sons.get(i).value; if (nextRoot != root) { maxx = Math.max(maxx, dfs(nextRoot)); } } return maxx + 1; } } }

这次的试题好难，没考虑到0不一定是根节点 另外问答题 高可用技术原理什么的完全没接触过，估计跪了。 话说编程题提交的时候系统有提示说不能再修改.......

int root = - 1 ; for ( int i = 0 ; i < n; i++) { if (fathers[i] == - 1 ) { root = i; } } 找到根结点

我也是把0当做根了。。只过了10%

根不是0  时间复杂度

//树的深度 import java.util.*; public class Main{ public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin=new Scanner(System.in); int[] nn= new int[1001]; int i=0; int n=0; int count = cin.nextInt(); nn[i++] = count; while((count--)!=0) { n=cin.nextInt(); nn[i++]=n; } getlength(nn,i); } public static void getlength(int[] nn,int i){ int number = i-1; if(number==0){System.out.print(0);return;} else if(number==1){System.out.print(1);return;} else if(number>1&&number<5){System.out.print(2);return;} int start = 1; int censhu = 0; censhu = number/2; int hehe[][] = new int[censhu][2]; for(int i1=0;i1<censhu;i1++){ for(int j1=0;j1<2;j1++){ hehe[i1][j1] = nn[start]; start++; } } int maxlength1 = 2; for(int i2=0;i2<censhu-1;i2++){ for(int j2=i2+1;j2<censhu;j2++){ if(hehe[i2][1]==hehe[j2][0]){ maxlength1++; i2 = j2; } } } int maxlength2 = 2; for(int i3=1;i3<censhu-1;i3++){ for(int j3=i3+1;j3<censhu;j3++){ if(hehe[i3][1]==hehe[j3][0]){ maxlength2++; i3 = j3; } } } int maxlength = 0; if(maxlength1>maxlength2){ maxlength = maxlength1; }else{ maxlength = maxlength2; } System.out.print(maxlength); } }

# coding:utf-8 import sys Input = [] while True: line = sys.stdin.readline() if not line: break Input.append(line.split('\n')) num = Input.pop(0) node = [] for i in xrange(len(Input)): node.append(Input[i][0].split(' ')) print node ＃ 建立树节点字典 shu_dict = {} for i in xrange(len(node)): shu_dict[int(node[i][1])] = int(node[i][0]) all_high = [] if num == 1: print 1 else: for key in shu_dict.keys(): high = 2 while shu_dict[key] != 0: high += 1 key = shu_dict[key] all_high.append(high) print max(all_high)

var n = parseInt(read_line()), line, list = [0]; for(var k = 1; k < n; k++){ var arr = read_line().split(' '); list[parseInt(arr[1])] = parseInt(arr[0]); } function find(child, len){ len++; if(!child){ return len; }else{ return find(list[child], len); } } var lenList = []; for(var i = 0; i < n; i++){ lenList.push(find(list[i], 0)); }; print(Math.max.apply(null, lenList));