题面
描述
根据输入数据建立一棵n个结点的二叉树,编号为1到n,其中编号为1的结点是根。编写程序求出二叉树的高度。
二叉树的高度定义:叶结点高度为1,自底向上逐层累加,根节点的高度即为树的高度。
输入
第一行一个正整数n,表示结点的个数
n行,第i行第一个数l表示第i个结点左孩子的序号,第二个数r表示第i个结点右孩子的序号,-1表示空
输出
本树的高度
思路
[v_error]树的高度有两种定义,根节点为0或1,本题已给出明确说明[/v_error]
如题中的树
而二叉树的高度定义:叶结点高度为1,自底向上逐层累加,根节点的高度即为树的高度。
那么我们就可以采用分治的算法,将左右子树分别取高度,然后取其最大值+1即为本节点高度,如此分治到根节点即可。
本节点高=最大值(获得左子树高,获得右子树高)+1
最终代码
[v_blue]请根据编译器(OJ)需要添加C++11的引用[/v_blue]
#include<bits/stdc++.h> using namespace std; struct node { int val; int l, r; }; unordered_map<int,node> tree; int n; int ans=INT_MIN; int geth(int root) { if (root == -1) return 0; int ll=geth(tree[root].l); int rr=geth(tree[root].r); int tmp = max(ll,rr)+1; return tmp; } int main() { cin >> n; for (int i = 1; i <= n; i++) { scanf("%d %d", &tree[i].l, &tree[i].r); } cout<<geth(1); return 0; }