二叉树的高度

Question

题目描述：
现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度
输入：输入的第一行表示节点的个数n（1<=n<=1000，节点的编号为0到n-1）组成，
下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号
输出树的高度，为一个整数
样例输入：
5
0 1
0 2
1 3
1 4
样例输出
3

Answer 1

递归，先求左子树的高度，再求右子树的高度，总的高度为它们最大值加1

Answer 2

这个……我笔试的时候碰到这个题了……（忘了是小米还是滴滴出行）直接上源码吧……

#include <iostream>
#include <vector>
#include <set>
#include <cstdio>

using namespace std;

int height(int root, vector<int> &lch, vector<int> &rch) {
    int n = lch.size();
    if (root < 0 || root >= n) { return -1; }
    if (lch[root] < 0 && rch[root] < 0) { return 1; }
    if (lch[root] < 0 || rch[root] < 0) {
        if (lch[root] >= 0) { return 1+height(lch[root], lch, rch); }
        if (rch[root] >= 0) { return 1+height(rch[root], lch, rch); }
    }
    return max(height(lch[root], lch, rch), height(rch[root], lch, rch)) + 1;
}

int main() {
    int n;
    while (1 == scanf("%d", &n)) {
        vector<int> lch(n, -1), rch(n, -1);
        set<int> ps, cs;
        for (int i = 0; i < n - 1; ++i) {
            int p, c;
            scanf("%d %d", &p, &c);
            ps.insert(p); cs.insert(c);
            if (lch[p] < 0) { lch[p] = c; continue; }
            if (rch[p] < 0) { rch[p] = c; continue; }
        }

        int root = -1;
        for (auto p : ps) {
            if (!cs.count(p)) {
                root = p;
                break;
            }
        }
        cout << height(root, lch, rch) << "\n";
    }
}

笔试的时候是通过的。

Answer 3

构建树，找root，遍历。

#include <functional>
#include <iostream>
#include <algorithm>
#include <map>
//#include <unordered_map>
using namespace std;
#define NULL 0
class Solution
{
public:
    int solve()
    {
        struct node
        {
            node*left = NULL, *right = NULL;
        };
        map<int, node*>tree_node;
        int fa[1001];
        for (int i = 0; i < 1001; i++)fa[i] = i;
        function<int(int)> find_root = [&](int i)
        {
            if (fa[i] != i)
                fa[i] = find_root(fa[i]);
            return fa[i];
        };
        int n;
        cin >> n;
        for (int i = 1; i < n; i++)
        {
            int f, c;
            cin >> f;
            node *father, *child;
            if (!tree_node[f])father = new node;
            else father = tree_node[f];
            cin >> c;
            if (!tree_node[c])child = new node;
            else child = tree_node[c];
            if (father->left == NULL)father->left = child;
            else father->right = child;
            tree_node[f] = father;
            tree_node[c] = child;
            fa[c] = find_root(f);
        }
        node *root = tree_node[find_root(0)];
        int result = 0;
        function<void(node*, int)>dfs = [&](node *now_node, int deep)
        {
            if (now_node == NULL)return;
            result = max(result, deep + 1);
            dfs(now_node->left, deep + 1);
            dfs(now_node->right, deep + 1);
        };
        dfs(root, 0);
        return result;
    }
};

Answer 4

int btHeight(int len, int[][] tree) {
    int *arr, i, height;
    if ((arr = malloc(sizeof(int[len]))) == NULL)
        return -1;
    memset(arr, 0, sizeof(int[len]);
    for (i = 0; i < len; i++)
        arr[tree[i][1]] = arr[tree[i][0]] + 1;
    for (i = height = 0; i < len; i++)
        height = max(height, arr[i]);
    return height + 1;
}