十道题带你手撕二叉树

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

1. 单值二叉树

题目:

十道题带你手撕二叉树

思路一:(遍历的方法

将根节点的值与二叉树中的每一个节点存储的val值进行比较,如果不同就返回false,如果全部相同,就返回true。

代码:

bool _isUnivalTree(struct TreeNode*root,int num)//辅助函数
{
    if(root == NULL)//只有一个节点或者递归调用到叶子节点的字节点时
        return true;
    else if(root->val == num)//当前根节点的值与存储的初始根节点的num相同的时候,此时就不需要返回true,因为当前根节点存储的值与初始节点存储的值相同并不代表后续节点的值也相同
    {
        return _isUnivalTree(root->left,num) && _isUnivalTree(root->right,num);
    }
    else//此情况就是root->val!=num的时候
        return false;
}
bool isUnivalTree(struct TreeNode* root)
{
    return _isUnivalTree(root,root->val);//调用辅助函数
}

思路二:

判断当前根节点的值是否与其左右子节点的值相等,如果不相等就返回false,同样,如果递归调用到了节点为空节点时就返回true

代码:

bool isUnivalTree(struct TreeNode* root)
{
    //空树复合题目的要求
    if(root==NULL)
    {
        return true;
    }
    
    //判断根节点与其左右子节点是否一样
    if(root->left&&root->left->val!=root->val)
    {
        return false;
    }
    if(root->right&&root->right->val!=root->val)
    {
        return false;
    }
    
    //判断左右子树
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

问:为什么只需要判断根节点和左右子节点是否一样就可以了?

答:注意这个-传递性,如果根节点和其左右子节点分别相同了,那么在递归的时候,之前的左右子节点就会变成根节点,此时就是在保持前面一样的前提下来判断新的根节点和新的根节点的左右子节点是否相同,优点类似链表,就是说链表的第一和第二个节点是相同的之后,然后判断第二和第三个节点是否是相同的,如果第二和第三个节点是相同的之后,那么第一和第三个节点也必然是相同的,依此类推,当这样的每个比较都成立之后,就说明整个二叉树就是等值二叉树。

当然,还有一种不是很好的写法,这种写法虽然也能通过,和上面的思路来说本质上并没有太大的区别(甚至定义的那个全局变量还显得有些多余),并不推荐这种写法,因为这种写法定义了一个全局变量,在OJ题中最好不要定义全局变量和静态变量,因为后台程序可能会多次调用这个程序,flag中可能还存储着上一次的结果,在下一次调用时容易出问题。代码如下:

bool flag = true;//默认最开始就是单值二叉树
bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        flag = true;
        return flag;
    }
    
    if(root->left && root->val!=root->left->val)
    {
        flag = false;
        return flag;
    }
    if(root ->right &&root->val!=root->right->val )
    {
        flag = false;
        return flag;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2. 相同的树

题目:

十道题带你手撕二叉树

代码:

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    //都是空树
    if(p==NULL&&q==NULL)
        return true;

    //有一个为空
    if(p == NULL || q == NULL)
        return false;

    //都不为空
    if(p->val!=q->val)
        return false;

    //递归比较左右子树
    return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
}

3. 对称二叉树

题目:

十道题带你手撕二叉树

代码:

bool isSymmetricTree(struct TreeNode* p,struct TreeNode* q)//辅助函数
{
    //两个节点均为空的情况
    if(p==NULL && q==NULL)
    {
        return true;
    }

    //两个节点有一个不为空的情况
    if(p == NULL || q == NULL)
    {
        return false;
    }

    //两个节点是否相等的情况并对两个节点进行递归判断,注意镜像相反
    return p->val == q->val && isSymmetricTree(p->left,q->right)&&isSymmetricTree(p->right,q->left);
}

bool isSymmetric(struct TreeNode* root){
    //根节点为空的情况
    if(root == NULL)
    {
        return true;
    }

    //根节点不为空的情况
    return isSymmetricTree(root->left,root->right);
}

4. 二叉树的前序遍历

题目:

十道题带你手撕二叉树

代码:

int BTreeSize(struct TreeNode* root)//计算二叉树元素的数目
{
    return root == NULL ? 0 : 1 + BTreeSize(root->left) + BTreeSize(root->right);
}

void _preorder(struct TreeNode* root,int *a,int *i)//辅助函数
{
    if(root == NULL)//空的时候直接返回
    {
        return;
    }
    //1.先遍历根节点
    a[*i] = root->val;//将有值得存储到开辟得数组空间中
    (*i)++;//数组下标进行自增操作
    //2.遍历左子树
    _preorder(root->left,a,i);//对左子树进行操作
    //3.遍历右子树
    _preorder(root->right,a,i);//对右子树进行操作
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int count = BTreeSize(root);//计算题目所给二叉树元素得数目
    int *a = malloc(sizeof(int)*count);//开辟数组存储二叉树元素
    assert(a);//防止malloc开辟失败
    *returnSize = count;//存储数组元素得数目
    int i = 0;//当作数组下标来存储二叉树元素
    _preorder(root,a,&i);
    return a;
}

5. 二叉树的中序遍历

题目:

十道题带你手撕二叉树

代码:

 int BTreeSize(struct TreeNode* root)//计算二叉树元素的数目
{
    return root == NULL ? 0 : 1 + BTreeSize(root->left) + BTreeSize(root->right);
}

void _inorder(struct TreeNode* root,int *a,int *i)//辅助函数
{
    if(root == NULL)//空的时候直接返回
    {
        return;
    }
    //1. 遍历左子树
    _inorder(root->left,a,i);//对左子树进行操作
    //2.遍历根节点
    a[*i] = root->val;//将有值得存储到开辟得数组空间中
    (*i)++;//数组下标进行自增操作
    //3.遍历右子树
    _inorder(root->right,a,i);//对右子树进行操作

}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int count = BTreeSize(root);//计算题目所给二叉树元素得数目
    int *a = malloc(sizeof(int)*count);//开辟数组存储二叉树元素
    assert(a);//防止malloc开辟失败
    *returnSize = count;//存储数组元素得数目
    int i = 0;//当作数组下标来存储二叉树元素
    _inorder(root,a,&i);
    return a;
}

6. 二叉树的后序遍历

题目:

十道题带你手撕二叉树

代码:

int BTreeSize(struct TreeNode* root)//计算二叉树元素的数目
{
    return root == NULL ? 0 : 1 + BTreeSize(root->left) + BTreeSize(root->right);
}

void _postorder(struct TreeNode* root,int *a,int *i)//辅助函数
{
    if(root == NULL)//空的时候直接返回
    {
        return;
    }
    //1. 遍历左子树
    _postorder(root->left,a,i);//对左子树进行操作
    //2.遍历右子树
    _postorder(root->right,a,i);//对右子树进行操作
    //3.遍历根节点
    a[*i] = root->val;//将有值得存储到开辟得数组空间中
    (*i)++;//数组下标进行自增操作
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int count = BTreeSize(root);//计算题目所给二叉树元素得数目
    int *a = malloc(sizeof(int)*count);//开辟数组存储二叉树元素
    assert(a);//防止malloc开辟失败
    *returnSize = count;//存储数组元素得数目
    int i = 0;//当作数组下标来存储二叉树元素
    _postorder(root,a,&i);
    return a;
}

7. 另一棵树的子树

题目:

十道题带你手撕二叉树

代码:

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    //都是空树
    if(p==NULL&&q==NULL)
        return true;

    //有一个为空
    if(p == NULL || q == NULL)
        return false;

    //都不为空
    if(p->val!=q->val)
        return false;

    //递归比较左右子树
    return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;
    return isSameTree(root,subRoot) || isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

8. 二叉树的遍历

题目:

十道题带你手撕二叉树

代码:(思路仍然是利用递归的思想)

#include<stdio.h>
#include<stdlib.h>
typedef struct BTreeBode
{
    char data;
    struct BTreeNode*left;
    struct BTreeNode*right;
}BTNode;

BTNode* CreateTree(char *a,int *pi)
{
    if(a[*pi]== '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = malloc(sizeof(BTNode));//创建节点
    root->data = a[(*pi)++];
    
    root->left = CreateTree(a,pi);
    root->right = CreateTree(a,pi);
    
    return root;
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
int main()
{
    char str[100];
    scanf("%s",str);
    int i = 0;
    BTNode* tree = CreateTree(str,&i);
    InOrder(tree);
    return 0;
}

9. 翻转二叉树

思路:是利用递归的思想,就是将每个二叉树看成是左子树 + 根节点 + 右子树
左子树又可以看成是:左子树 = 左子树 + 根节点 + 右子树
右子树又可以看成是: 右子树 = 左子树 + 根节点 + 右子树

然后将左右子树分别互换即可,从最小的子树开始思考:

十道题带你手撕二叉树

上面的子树中,2有两个子节点3和1,所以将3节点和1节点进行互换即可,然后对于整个二叉树来说,也都是将左子树和右子树进行互换即可。

十道题带你手撕二叉树

代码:

struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)//空指针时返回
    {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);//左子树
    struct TreeNode* right = invertTree(root->right);//右子树
    root->left = right;
    root->right = left;
    return root;
}

10. 二叉树的销毁

注意:二叉树的销毁只能采取后序遍历的方式进行销毁,因为一旦根节点被销毁后,就无法找到子节点的地址了。文章来源地址https://www.toymoban.com/news/detail-402535.html

void BinaryTreeDestory(BTNode** root)
{
	if ((*root) == NULL)//判断是否为空,如果为空直接返回
	{
		return;
	}
	//此处采用后序遍历的方法,因为根必须留在最后销毁
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

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

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

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

相关文章

  • 手撕二叉平衡树

    今天给大家带来的是平衡树的代码实现,如下: 这个仅仅是平衡树的插入,其实二叉平衡树的插入并不难,逻辑就是那么几个,但是难得是细节处的实现,尤其是平衡因子更新的那一块,特别的容易弄混人,只要记住四种模型就可以了。两种单旋,两种双旋,还是有点难以理

    2024年02月10日
    浏览(36)
  • [C语言实现]带你手撕带头循环双链表

    目录 什么是双链表? 带头结点的优势: 双链表的实现: 众所周知,顺序表的插入和删除有时候需要大量移动数据,并且每次开辟空间都可能会浪费大量内存和CPU资源,于是我们有了链表,我们之前已经实现了单链表,我们可以发现单链表的一个劣势——每次查找都必须从头结

    2024年02月06日
    浏览(42)
  • 【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)

    欢迎来到 Claffic 的博客  💞💞💞 “东风随春归,发我枝上花。” 前言:  排序是日常生活中极其常见的一种算法,它的功能很简单,就是将数字按照升序/降序排列,最终形成一组有序的数字,不过形成有序数字的过程有多种实现方式,它们各有好坏,接下来,由我带你手

    2023年04月19日
    浏览(45)
  • Day15|leetcode层序遍历(10道题)、226.翻转二叉树、101.对称二叉树

    视频链接:讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode:102.二叉树的层序遍历_哔哩哔哩_bilibili 看完视频可以一口气做十道题!(102、107、199、637、429、515、116、117、104、111) 二叉树的层序遍历如图所示: 题目链接:226. 翻转二叉树 - 力扣(LeetCode) 视频链接:听说一位

    2024年02月11日
    浏览(79)
  • 力扣256.翻转二叉树(递归/qBFS) 剑指offer 32 从上到下打印二叉树(q BFS)I II III(三道题)

    采用队列 采用递归 第一个需要考虑的问题是 二维数组怎样在不知道行和列的情况下进行插入 :先定义一维数组,然后将一维数组插入二维数组! 第二个需要考虑的问题是 BFS中队列进行遍历每一层的时候既需要把当前结点的左右孩子结点存到队列里,同时当前层结束后 原来

    2024年02月16日
    浏览(43)
  • 手撕链式二叉树(二)—【C语言】

    链式二叉树(一)         http://t.csdn.cn/HWu6E 目录 1. 二叉树找值为x的节点 代码实现分析  代码实现 递归展开图 2. 求二叉树层数 代码思路分析 代码实现   3. 二叉树的销毁 代码思路分析 代码实现 运行结果 4. 二叉树的一些OJ题目 1. 单值二叉树                      OJ链接

    2024年02月06日
    浏览(51)
  • 数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解(含每道题链接及递归图解)

    有没有一起拼用银行卡的,取钱的时候我用,存钱的时候你用 难度等级:⭐ 直达链接:相同的树 难度等级:⭐ 直达链接:单值二叉树 难度等级:⭐⭐ 直达链接:对称二叉树 难度等级:⭐⭐⭐ 直达链接:二叉树的前序遍历 难度等级:⭐⭐⭐⭐ 直达链接:另一颗子树 注:

    2024年04月16日
    浏览(80)
  • 数据结构---手撕图解二叉树(含大量递归图解)

    二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根… 因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的

    2024年02月16日
    浏览(42)
  • 数据结构:手撕图解二叉树(含大量递归图解)

    二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根… 因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的

    2024年02月15日
    浏览(52)
  • 二叉树详解:带你掌握二叉树

    因为二叉树是一种特殊的树,所以想要学习好二叉树,必须了解树型结构,知道树的基本概念。所以正式开始学习之前,在前面为大家引入了树的概念。 1. 1 树的概念 树是一种 非线性 的数据结构,它是有n个节点构成的集合,把它称为树,是因为这种结构看起来就像一个 倒

    2024年02月08日
    浏览(30)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包