牛客网-树的高度（小米）

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

5
0 1
0 2
1 3
1 4

输出

3

思路：根据给定的结点关系，建立树，然后再计算树的高度

#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
struct node{
    int val;
    node *lchild;
    node *rchild;
   
    node(int val): val(val){
        lchild = NULL;
        rchild = NULL;
    }
};
   
void createTree(node *root, int father, int child){
    if(root == NULL)
        return;
    if(root->val == father){
        if(root->lchild == NULL)
            root->lchild = new node(child);
        else if(root->rchild == NULL)
            root->rchild = new node(child);
        return;
    }
    createTree(root->lchild, father, child);
    createTree(root->rchild, father, child);
}
   
int getHeight(node *root){
    if(root == NULL)
        return 0;
    int l = getHeight(root->lchild);
    int r = getHeight(root->rchild);
    return l > r ? (l+1) : (r+1);
}
   
int main() {
   
    int n;
    int father, child;
    while(cin>>n){
        cin>>father>>child;
        node *root = new node(father);
        createTree(root, father, child);
        for(int i = 1; i < n-1; i++){
            cin >> father >> child;
            createTree(root, father, child);
        }
   
        cout << getHeight(root) << endl;
    }
    return 0;
}