欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

练习题二:树的高度

程序员文章站 2022-05-24 17:31:03
题目描述 现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度 输入描述: 输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号。 输出描述 ......

题目描述

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

输入描述:

输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,

下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号。

输出描述:

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

Python解法

# -*- coding:utf-8 -*-
import sys


def tree_height(root):
  if len(tree[root]) == 0:
    return 1
  node_list = []
  for i in tree[root]:
    node_list.append(tree_height(i))
  return max(node_list) + 1


if __name__ == "__main__":
  n = sys.stdin.readline().strip()
  tree = []
  for i in range(int(n)):
    tree.append([])
  for i in range(int(n)-1):
    father, child = map(int, sys.stdin.readline().strip().split())
    if len(tree[father]) <= 1 :
      tree[father].append(child)
  print(tree_height(0))