树的高度问题

Question

现在有一颗合法的二叉树，树的节点都是数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度。

输入的第一行表示节点个数为n，节点的编号为0到n-1组成，下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出树的高度，为一个整数。

样例输入：
5
0 1
0 2
1 3
1 4

样例输出: 3

Answer 1

贴一个自己的满分解答

关于找根节点的问题，每次碰到一个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;
}

Answer 2

你是在小米笔试吗

Answer 3

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

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

Answer 4

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

Answer 5

自己运行都是正确的，提交上去只有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;
}

Answer 6

怎么找根节点？
写的代码 过了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;
}

Answer 7

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

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

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

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

Answer 8

这个代码就是平台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;
}

Answer 9

这个有人会js写法吗

Answer 10

case通过率为50.00%,有没有大佬看看。

function Node(value){
    this.value = value;
    this.children = []; 
}

var n = readline();

var m = n - 1;

var arr = [];

while(m){
    
    m--;
    
    var t = readline().split(' ');
    
    var nodeP = arr.find(v => v.value === t[0]);
    
    if(!nodeP){
        nodeP = new Node(t[0]);
        arr.push(nodeP);
    }
    
    var nodeC = arr.find(v => v.value === t[1]);
    if(!nodeC){
        nodeC = new Node(t[1]);
        arr.push(nodeC);
    }
    
    if(!nodeP.children.find(v => v.value === nodeC.value)){
        nodeP.children.push(nodeC);
    }    
}

 
var root = (function(arr){
    for(var i = 0, l = arr.length; i < l; i++){
       if(arr[i].children.length > 0){
          arr[i].children.forEach(v => v.isChild = true);
       }
    }
    return arr.find(v => !v.isChild);
})(arr);


var height = []; 

(function calculateHeight(root,h){
     if(root.children.length > 0){
         h++;
         root.children.forEach( n => calculateHeight(n,h));
     }else{
         height.push(h);
     }
})(root,1);
 
console.log(Math.max.apply(null,height));