248-求二叉树的深度(高度)

你的名字 2022-11-14 10:23 156阅读 0赞

## 求二叉树的深度(高度) ##

## 递归算法 ##

![在这里插入图片描述][20210328203901779.png_pic_center]  
解题思路：  
**先算出左子树的高度和右子树的高度，然后进行对比，拿较高的那个值加1就是此二叉树的深度(高度)了！！！**

int GetDepth(BtNode* ptr)
    {
        
    	if(ptr==nullptr)
    		return 0;
    	else
    		return std::max(GetDepth(ptr->leftchild),GetDepth(ptr->rightchild))+1;
    }

## 非递归算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**利用层次遍历，打印1层，加1，以此类推**  
**我们使用队列，全部出完1层，加1，关键是我们得知道这一层中有多少个数据节点。**

int GetNiceDepth(BtNode* ptr)
    {
        
    	int sum=0;
    	if(ptr==nullptr) return sum;
    	std::queue<BtNode*> qu;
    	qu.push(ptr);
    	while(!qu.empty())
    	{
        
    		int n=qu.size();
    		while(n--)
    		{
        
    			ptr=qu.front(); qu.pop();
    			if(ptr->leftchild!=nullptr) qu.push(ptr->leftchild);
    			if(ptr->rightchild!=nullptr) qu.push(ptr->rightchild);
    		}
    		sum+=1;
    	}
    	return sum;
    }

[20210328203901779.png_pic_center]: /images/20221022/1a1c29cc00584896982288f400bf34d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210328204647334.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center

发表评论取消回复

表情：

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

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

相关阅读

相关二叉树深度和高度_二叉树的高度和深度

![208b9eac8e4029f24bebf06a7ac44c80.png][] 二叉树深度和高度 In this tutorial, we will learn how

忘是亡心i/ 2022年12月07日 12:56/ 0 赞/ 207 阅读

相关 248-求二叉树的深度(高度)

求二叉树的深度(高度) 递归算法 ![在这里插入图片描述][20210328203901779.png_pic_center] 解题思路：先算出左子树的高

你的名字/ 2022年11月14日 10:23/ 0 赞/ 157 阅读

相关求二叉树的深度

求二叉树的深度 Time Limit: 1000MS Memory limit: 65536K 题目描述已知一颗二叉树的中序遍历序列和后序遍历序列，

超、凢脫俗/ 2022年09月25日 04:26/ 0 赞/ 181 阅读

相关求二叉树的深度

Problem Description 已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。 Input 输入数据有多组，输入T，代表有T组数据。每组数据

淡淡的烟草味﹌/ 2022年07月12日 03:20/ 0 赞/ 210 阅读

相关求二叉树的深度

Problem Description 已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。 Input 输入数据有多组，输入T，代表有T组数据。每组数据

谁践踏了优雅/ 2022年07月12日 03:20/ 0 赞/ 220 阅读

相关求二叉树的深度

[sdut原题链接][sdut] 求二叉树的深度 Time Limit: 1000MS Memory Limit: 65536KB Problem Descriptio

偏执的太偏执、/ 2022年07月12日 02:42/ 0 赞/ 214 阅读

相关求二叉树的高度

/求二叉树的高度/ include<stdio.h> typedef struct btnode { char data;

约定不等于承诺〃/ 2022年06月16日 13:44/ 0 赞/ 180 阅读

相关求二叉树的深度

一、二叉树深度和高度概念一般书籍都是表示:二叉树的最大层数,高度即:从叶子节点往根节点数，深度则相反. 如图:二叉树的深度和高度都为3 ![这里写图片描述][70]

超、凢脫俗/ 2022年05月25日 11:40/ 0 赞/ 214 阅读

相关求二叉树的深度

题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 class TreeNode:

怼烎@/ 2022年04月04日 14:29/ 0 赞/ 241 阅读

相关求二叉树高度PTA

本题要求给定二叉树的高度。函数接口定义： int GetHeight( BinTree BT ); 其中BinTree结构定义如下： typede

待我称王封你为后i/ 2022年02月04日 04:19/ 0 赞/ 395 阅读