84669 orang belajar
152542 orang belajar
20005 orang belajar
5487 orang belajar
7821 orang belajar
359900 orang belajar
3350 orang belajar
180660 orang belajar
48569 orang belajar
18603 orang belajar
40936 orang belajar
1549 orang belajar
1183 orang belajar
32909 orang belajar
题目描述:现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度输入:输入的第一行表示节点的个数n(1<=n<=1000,节点的编号为0到n-1)组成,下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号输出树的高度,为一个整数样例输入:50 10 21 31 4样例输出3
欢迎选择我的课程,让我们一起见证您的进步~~
递归,先求左子树的高度,再求右子树的高度,总的高度为它们最大值加1
这个……我笔试的时候碰到这个题了……(忘了是小米还是滴滴出行)直接上源码吧……
#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"; } }
笔试的时候是通过的。
构建树,找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; } };
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; }
递归,先求左子树的高度,再求右子树的高度,总的高度为它们最大值加1
这个……我笔试的时候碰到这个题了……(忘了是小米还是滴滴出行)直接上源码吧……
笔试的时候是通过的。
构建树,找root,遍历。