贴一个自己的满分解答

关于找根节点的问题，每次碰到一个a -> b的边，b就被标记一下不是根节点，
最后找出唯一一个没有被标记的点就好了。

#include <bits/stdc++.h>
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
using namespace std;
vector<vector<int> > g;
int solve(int pos) {
    int ret = 0;
    FOR(i, g[pos].size()) {
        ret = max(ret, solve(g[pos][i]));
    }
    return ret + 1;
}
int main() {
    int n, from, to;
    cin >> n;
    FOR(i, n) g.push_back(vector<int>());
    vector<bool> root(n, true);
    FOR(i, n - 1) {
        cin >> from >> to;
        root[to] = false;
        g[from].push_back(to);
    }
    FOR(i, n) {
        if (root[i]) {
            cout << solve(i) << endl;
            break;
        }
    }
    return 0;
}

你是在小米笔试吗

没说根结点是哪个怎么做...

找一个度不为三的点作DFS就好了

这个有人会js写法吗

自己用node运行试了用例可以，但是放上去就报错....哭~

自己运行都是正确的，提交上去只有10%的正确率，心累.
谁帮我看一看哪里还有错误？我也找到根节点了的。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main{
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        BinaryTreeNode[] nodes = new BinaryTreeNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new BinaryTreeNode();
            nodes[i].value = 1;
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        for (int i = 0; i < n - 1; i++) {
            int a = s.nextInt();
            int b = s.nextInt();
            set1.add(a);
            set2.add(b);
            if (nodes[a].leftNode == null) {
                nodes[a].leftNode = nodes[b];
            } else {
                nodes[a].rightNode = nodes[b];
            }
        }
        for (Integer i : set2) {
            if (set1.contains(i)) {
                set1.remove(i);
            }
        }
        int index = 0;
        for (Integer integer : set2) {
            index = integer;
        }
        System.out.println(getMaxHeight(nodes[index]));
    }

    public static int getMaxHeight(BinaryTreeNode root) {
        if (root == null)
            return 0;
        else {
            int left = getMaxHeight(root.leftNode);
            int right = getMaxHeight(root.rightNode);
            return 1 + Math.max(left, right);
        }
    }
}

class BinaryTreeNode {
    int value;
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
}

求一个答案啊

怎么找根节点？
写的代码 过了10%的样例，应该是没找到根节点

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n;
vector<vector<int>> rd(1000);
int maxNum = 0;
void Dfs(int s, int d){
    if(rd[s].empty()){
        if (d > maxNum) maxNum = d;
        return;
    }
    for(int i = 0; i < rd[s].size(); i++)
        Dfs(rd[s][i], d+1);
}

int main(){
    cin >> n;
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        rd[a].push_back(b);
    }
    Dfs(0, 1);
    cout << maxNum << endl;
    return 0;
}

1. 既然有了父子关系，就说明从子节点可以找到父节点

2. 用一个数组保存父子关系，array[childNo]=fatherNo（array[]初始化为全-1）

3. 找到每个节点所在的层数：
   从这个节点开始，利用array[]找他的父节点，不停的向上找，每向上一层count就+1，一直找到根节点为止（array[child]==-1），这个时候count+1就是节点在的层数

4. 找出所有节点所在层数的最大值就是树的高度（应该可与不用求所有节点的层数）

这个代码就是平台AC过的，其中根结点是根据0到n-1的和减去右侧一列的值所得的差值即为根结点。

#include<iostream>

using namespace std;

int calcDeep(int curNode, int data[][2], int cur){
    if(data[curNode][0] == -1)
        return cur;
    int left = calcDeep(data[curNode][0], data, cur+1);
    int right = 0;
    if(data[curNode][1] != -1){
        right = calcDeep(data[curNode][1], data, cur+1);
    }
    return left>right ? left : right;
}
int main(){
    int n;
    cin>>n;
    if(n == 1){
        cout<<"1";
        return 0;
    }
    int temp = n-1;
    int (*data)[2] = new int[n][2];
    for(int i=0; i<n; i++){
        data[i][0] = -1;
        data[i][1] = -1;
    }
    int sum = 0;
    int t1,t2;
    for(int index=0; index<temp; index++){
        cin>>t1>>t2;
        sum += t2;
        if(data[t1][0] == -1){
            data[t1][0] = t2;
        }
        else{
            data[t1][1] = t2;
        }
    }
    int root = ((n-1)*n)/2 - sum;
    int deep = calcDeep(root, data, 1);
    cout<<deep;
    // system("pause");
    return 0;
}