OJ 树的高度 C++ python

待我称王封你为后i 2022-05-19 00:35 171阅读 0赞

*  题目描述

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

*  输入描述

输入的第一行表示节点的个数n（1 ≤ n ≤ 1000，节点的编号为0到n-1）组成，
    下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

*  输出描述

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

*  输入

5
    0 1
    0 2
    1 3
    1 4

*  输出

3

--------------------

**python代码**

n = int(input())
    high = [1] * n
    num = [0] * n
    for i in range(n - 1):
        parent, children = map(int, input().split()) #map会根据提供的函数对指定的序列做映射
        if num[parent] < 2 :
            high[children] = high[parent] + 1
            num[parent] += 1
        else :
            num[parent] = 2   #防止不合法的二叉树的高度继续增加
            num[children] = 2
    print(max(high))

**C++代码**

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int n, parent, children;
        cin >> n;
        vector<int> high(n); //需要预先声明size
        vector<int> num(n);
        high[0] = 1;
        num[0] = 0;
        for(int i = 0;i < n - 1;i ++){
            cin >> parent;
            cin >> children;
            if(num[parent] < 2){
                high[children] = high[parent] + 1;
                num[parent] += 1;
            }
            else{
                num[parent] = 2;
                num[children] = 2;
            }
        }
        auto maxElem = max_element(high.begin(), high.end());  //判断数组中最大最小值的函数
        cout << * maxElem;
    }

**算法思想**

维护两个数组，一个数组存储高度，一个数组存储当前节点的子节点数目，当子节点超过两个的时候，要进行剪枝

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】二叉搜索树经典OJ题目

文章目录根据二叉树创建字符串二叉树的层序遍历二叉树的层序遍历II 二叉树的最近公共祖先二叉搜索树与双向链表从前序与中序遍历序

浅浅的花香味﹌/ 2023年09月26日 22:12/ 0 赞/ 154 阅读

相关 python-二叉树的实现(oj向)

目录前言基本操作函数创建遍历先序遍历（递归）中序遍历（递归）后序遍历（递归）层次遍历（迭代）高度高级操作函数锯齿形遍历全部代码

末蓝、/ 2022年12月30日 03:42/ 0 赞/ 164 阅读

相关树的高度

题目描述现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度输入描述: 输入的第一行表示节点的个数n（1 ≤

爱被打了一巴掌/ 2022年06月03日 05:39/ 0 赞/ 168 阅读

相关求树的高度

题目：树的高度时间限制：C/C++语言 1000MS；其他语言 3000MS 内存限制：C/C++语言 65536KB；其他语言 589824KB 题目描述：

拼搏现实的明天。/ 2022年05月28日 04:29/ 0 赞/ 165 阅读

相关 OJ数串 c++ python

题目描述设有n个正整数，将他们连接成一排，组成一个最大的多位整数。如:n=3时，3个整数13,312,343,连成的最大整数为34331213。

今天药忘吃喽~/ 2022年05月23日 13:55/ 0 赞/ 204 阅读

相关 OJ水仙花数 C++ python

题目描述春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的： “水仙花数”是指一个三位数，它的各位数字的立方和等于其

柔光的暖阳◎/ 2022年05月19日 04:13/ 0 赞/ 231 阅读

相关 OJ 树的高度 C++ python

题目描述现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度输入描述输入的第一行表示节点的个数

待我称王封你为后i/ 2022年05月19日 00:35/ 0 赞/ 172 阅读

相关数据结构-树的高度

【题目来自灰灰考研】（2017武汉科技大学初试）二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域Data，左孩子指针域left和右孩子指针域right。请设计

深碍√TFBOYSˉ_/ 2022年05月18日 02:53/ 0 赞/ 156 阅读

相关树的高度，树的深度

先定义树的根节点深度为1，高度基数为0。各节点在基数基础上加一或减一因此，各节点深度为红色数字，各节点高度为蓝色数字 ![70][] [70]: /imag

今天药忘吃喽~/ 2022年05月17日 02:20/ 0 赞/ 183 阅读

相关二叉树的高度

求二叉树的高度（递归）用递归求二叉树的高度，定义三个整形变量 HL（记录左结点是否存在，存在为1，不存在为0） HR （记录右结点是否存在，存在为1，不存在为0）

柔光的暖阳◎/ 2022年02月01日 09:51/ 0 赞/ 266 阅读