二叉树刷题专练(三)

这篇具有很好参考价值的文章主要介绍了二叉树刷题专练(三)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

二叉树刷题专练(三)


继承前面的写作思路,此篇文章继续二叉树的oj题

一、二叉树的最小深度

1.题目介绍

题目在力扣 二叉树的最小深度
二叉树刷题专练(三)

2.思路

最小深度是从根节点到最近叶子节点的最短路径上的节点数量,叶子节点是没有子节点的节点,那么叶子节点的是不是只可能出现在一个字数遍历完才会出现,所以这题我们就可以转化成一个遍历到叶子的最短路径,那么们就会出现下面这种情况,这种情况数出5,即返回右子树的最小深度二叉树刷题专练(三)
二叉树刷题专练(三)

所以我们可以总结成以下几点

1.如果root为空,则返回0;
2.如果左节点为空,那么直接返回右节点的最小深度+1即可
3.如果左节点为空,那么直接返回右节点的最小深度+1即可
4.如果两者都不为空,我们就返回左节点和右节点中小的那个节点+1

3.代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int minDepth(struct TreeNode* root){
    if(root==NULL)
    return 0;
    if(root->left==NULL)
    return minDepth(root->right)+1;
    else if(root->right==NULL)
    return minDepth(root->left)+1;
    int left=minDepth(root->left);
    int right=minDepth(root->right);
    if(left<right)
    {
        return left+1;
    }
    else
    {
        return right+1;
    }

}

二、完全二叉树的节点个数

1.题目介绍

题目在力扣完全二叉树的节点个数
二叉树刷题专练(三)

2.思路

本题考的就是层序遍历,将这课二叉树层序遍历一遍就行了,层序就是建立一个队列,利用队列的先进先出的性质,每pop一个节点,就依次带入其非NULL节点的左节点和右节点,如下图
二叉树刷题专练(三)
你可以用数组模拟队列,也可以直接拿队列的代码来弄文章来源地址https://www.toymoban.com/news/detail-407452.html

3.代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode* QDatatype;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype Data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;

}

void QueuePush(Queue* pq, QDatatype x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);
    newnode->Data = x;
    newnode->next=NULL;
    if (pq->size == 0)
    {
        pq->head =pq->tail= newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;

}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->size);
    if (pq->head->next==NULL)
    {
        free(pq->head);
        pq->head =pq->tail= NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->size==0;
}

QDatatype QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->Data;
}

QDatatype QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->Data;
}




int countNodes(struct TreeNode* root){
    if(root==NULL)
    return 0;
	Queue tree;
	Queue* pt = &tree;
	QueueInit(pt);
	QueuePush(pt,root);
    int count=0;
	while (!QueueEmpty(pt))
	{
		struct TreeNode* front = QueueFront(pt);
        count ++;
		QueuePop(pt);
		if (front->left)
		{
			QueuePush(pt, front->left);
		}
		if (front->right)
		{
			QueuePush(pt, front->right);
		}
	}
	QueueDestroy(pt);
    return count;
}

到了这里,关于二叉树刷题专练(三)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode刷题(7)二叉树(1)

    哈喽大家好,这是我leetcode刷题的第七篇,这两天我将更新leetcode上关于二叉树方面的题目,如果大家对这方面感兴趣的话,欢迎大家持续关注,谢谢大家。 那么我们就进入今天的主题。 leetcode之二叉树的前序遍历(难度:简单) 给你二叉树的根节点 root ,返回它节点值的

    2023年04月25日
    浏览(35)
  • leetcode刷题(10)二叉树(4)

    各位朋友们,大家五一劳动节快乐啊,在这里祝大家假期玩得愉快!但是在玩耍的期间不要忘记了敲代码哦。今天我为大家分享的是二叉树的第四篇,废话不多说,我们一起来看看吧。 leetcode之二叉树的最近公共祖先(难度:中等) 给定一个二叉树, 找到该树中两个指定节点

    2024年02月02日
    浏览(36)
  • leetcode刷题(8)二叉树(2)

    各位朋友们,大家好!今天我为大家分享的是关于二叉树leetcode刷题的第二篇,我们一起来看看吧。 leetcode之对称二叉树(难度:简单) 给你一个二叉树的根节点 root , 检查它是否轴对称。 输入:root = [1,2,2,3,4,4,3] 输出:true 这道题我们需要先判断二叉树的左子树的结构与右

    2023年04月24日
    浏览(32)
  • LeetCode刷题——617. 合并二叉树

    给你两棵二叉树: root1 和 root2 。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为

    2024年02月13日
    浏览(44)
  • 算法刷题Day 17 平衡二叉树+二叉树的所有路径+左叶子之和

    计算左右两棵子树的高度,如果有一个高度是-1(有一棵子树不平衡),直接返回-1,否则计算高度差,判断是否不平衡 使用 回溯 的方法,每次处理一个节点之前要把它push进table里,处理完之后又要把它pop出来 处理一个节点时,要判断它是否是左节点(需要父节点,可以通

    2024年02月15日
    浏览(43)
  • 二叉树与图(C++刷题笔记)

    力扣 从根节点深度遍历二叉树,先序遍历时,将节点存储至path栈中,使用path_val累加节点值 当遍历到叶子节点,检查path_val是否为sum,若是,则将pathpush进入res的结果中去 在后续变量,将该节点从path栈中弹出,path_val减去节点值 题目代码 力扣 两个节点公共祖先一定从根节点

    2024年02月05日
    浏览(41)
  • LeetCode刷题--- 二叉树的所有路径

    个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题       【     】 【C++】                  【   】 数据结构与算法       【    】 前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的

    2024年01月19日
    浏览(43)
  • 【数据结构刷题专题】—— 二叉树

    二叉树 二叉树刷题框架 二叉树的定义: 1 二叉树的遍历方式 【1】前序遍历 【2】后序遍历 【3】中序遍历 【4】层序遍历 2 二叉树的属性 【1】101. 对称二叉树 【2】104. 二叉树的最大深度 迭代法: 递归法: 【3】111.二叉树的最小深度 递归法: 迭代法: 【4】222. 完全二叉树的

    2024年04月10日
    浏览(43)
  • 跟着《代码随想录刷题》(六)—— 二叉树

    LeetCode:114、二叉树的前序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:94、二叉树的中序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:145、二叉树的后序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:589、N叉树前序遍历 LeetCode:590、N叉

    2024年02月09日
    浏览(47)
  • leetcode刷题记录:二叉树02(思路篇)

    参考labuladong的算法小抄:https://labuladong.online/algo/data-structure/binary-tree-part1/ 复习二叉树纲领篇,二叉树解题的思维模式分两类: 1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。 2、是否可以定义一个

    2024年02月19日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包