【信奥】求树的高度
本文最后更新于 647 天前,其中的信息可能已经有所发展或是发生改变。

题面

描述

根据输入数据建立一棵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;
}
本文由吕舒君创作,转载请保留链接
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇