IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> [C] PTA 6-8 求二叉树高度 -> 正文阅读

[C++知识库][C] PTA 6-8 求二叉树高度

本题要求给定二叉树的高度。

函数接口定义:

int GetHeight( BinTree BT ); 

其中BinTree结构定义如下:

typedef struct TNode *Position; 
typedef Position BinTree; 
struct TNode{ 
????ElementType Data; 
    BinTree Left; 
    BinTree Right; 
}; 

要求函数返回给定二叉树BT的高度值。

思路:

二叉树的高度就是根节点的高度。

已知当前结点高度=子树高度最大值+1,所以递归求一下左右子结点(左右子树)高度就好。

时间复杂度:O(N) N是结点数?

空间复杂度:O(N)

int GetHeight( BinTree BT ){
    int hl=0;
    int hr=0;
    int h=0;
    
    if(BT==NULL){
        return 0;
    }
    
    hl=GetHeight(BT->Left);//求左子树高度
    hr=(GetHeight(BT->Right));//求右子树高度
    
    if(hl>hr){
        h=hl+1;
    }else{
        h=hr+1;
    }
    return h;
}

以下是发文助手嫌我文章太短所以瞎打的字:

递归是比较容易理解的方式。

那么这道题除了递归还有其他的方法吗?

树的高度也可以理解为层数。可以尝试用层序遍历的思路求树的高度。

如果结点结构体里能有一个变量记录当前结点在第几层就好了——诶,data不就可以?毕竟这道题没要求输出结点的数据,所以data可以随便篡改

创建使用一个队列,根节点赋值为1,使其入队;左右孩子赋值为2,入队......

即:子节点data值=父节点data值+1,并进入队列。

设一个int变量h。对队列遍历,如果比h大就赋给h。

入队+出队的时间复杂度: O(N)

空间复杂度:O(N)

......真是没有必要的优化呢,优化了个寂寞

  C++知识库 最新文章
C陷阱与缺陷 第7章 可移植性缺陷 7.1 应对C
C语言犄角旮旯的知识之结构体
从零到一快速学会三子棋
【Codeforces Round #805 (Div. 3)(A~C)】
C++中static_cast和dynamic_cast强制类型转
【C++进阶知识继承】继承的赋值转换,菱形虚
D. Yet Another Sorting Problem
牛客华为C++笔试题目(一)
从零开始 学习C/C++的第二十二天 文件读写
2021-07-25
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 18:48:02  更:2022-06-29 18:48:18 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年8日历 -2022/8/8 0:08:11-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码