C语言进阶二叉树的基础与销毁及层序遍历详解

难度简单

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回true;否则返回false

示例 1:

输入:[1,1,1,1,1,null,1]
输出:true

示例 2:

输入:[2,2,2,5,2]
输出:false

提示:

给定树的节点数范围是[1, 100]

每个节点的值都是整数,范围为[0, 99]

解1:

最简单易懂的解法,先序遍历一遍,把每个节点都和那个根节点的val值相比。最后判断flag是否为真,若为假,则表明树中有某节点的值不符。

其中的return语句是为了避免一些无意义的比较,但是其实第一个if的flag判断完全可以写在左递归之后,判断一下,如果左递归将flag置为了假,则直接return,不会进入右子树。如果按照上方解法来说,就是进入右子树之后,发现flag为假,再退出。

OJ题里的全局变量需要小心使用,若isUnivalTree里的flag不置为真,则多个测试用例时,可能会承接上一个测试用例假的结果。发生错误。

解法2:

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(root == NULL)
            return true;
        if(root->left != nullptr && root->left->val != root->val)
            return false;
        if(root->right != nullptr && root->right->val != root->val)
            return false;
        return isUnivalTree(root->left)
            && isUnivalTree(root->right);
    }
};

判断每个结点和其两个子节点是否相同,当然,需要确保子节点非空,若存在不同的,直接返回false,然后递归其左右子树。

其实这个的实质就是前序遍历,对每个结点的操作就是比较它和两个子节点的值是否相同。每个结点如果都和其左右子结点相同,那么这棵树也就都相同了,如果某处不同,则返回false,层层返回,最终也会返回flase。

解法3:

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        bool ret = PreOrder(root, root->val);
        return ret;
    }
    bool PreOrder(TreeNode* root, int val)
    {
        if(root == nullptr)
            return true;
        if(root->val != val)
            return false;
        return PreOrder(root->left, val)
            && PreOrder(root->right, val);
    }
};

与2相比没什么大的改进,只是比较的方式不同而已,仍然是前序遍历的思想。 第三个return里的&&挺好,左是假则不会对右求值。

难度简单844

给你两棵二叉树的根节点pq,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]
​​​​​​​输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]
​​​​​​​输出:false

提示:

  • 两棵树上的节点数目都在范围[0, 100]
  • -104<= Node.val <= 104

通过次数344,943提交次数577,105

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr)
            return true;
        if(!(p!=nullptr && q!=nullptr && p->val == q->val))
            return false;
        bool retl = isSameTree(p->left,q->left);
        if(retl == false)
            return false;
        bool retr = isSameTree(p->right,q->right);
        if(retr == false)
            return false;
        return true;
/*
        return isSameTree(p->left,q->left)
            && isSameTree(p->right,q->right);
*/
    }
};

亿亿亿亿亿亿亿亿亿亿旧是前序遍历,只是两棵树同时遍历而已,判断是否相同,两个递归和最后那个注释的是效果相同的。

难度简单1942

给你一个二叉树的根节点root, 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3]
​​​​​​​输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]
​​​​​​​输出:false

提示:

  • 树中节点数目在范围[1, 1000]
  • -100 <= Node.val <= 100

进阶:你可以运用递归和迭代两种方法解决这个问题吗?

通过次数603,527提交次数1,044,923

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isSame(root->left, root->right);
    }
    bool isSame(TreeNode* root1, TreeNode* root2)
    {
        if(root1 == nullptr && root2 == nullptr)  // 都是空,结束递归,且符合条件
            return true;
        // 两者根节点不相等,结束,不需要进一步判断了。
        if(!(root1 != nullptr && root2 != nullptr && root1->val == root2->val))
            return false;
        // 进一步判断
        return isSame(root1->left,root2->right) && isSame(root1->right,root2->left);
    }
};

依旧是前序遍历。。。。。。。。。

难度简单739

给你两棵二叉树rootsubRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在,返回true;否则,返回false

二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。

示例 1:

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
​​​​​​​输出:true

示例 2:

输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
​​​​​​​输出:false

提示:

  • root树上的节点数量范围是[1, 2000]
  • ​​​​​​​subRoot树上的节点数量范围是[1, 1000]
  • ​​​​​​​-104<= root.val <= 104
  • -104<= subRoot.val <= 104

通过次数125,811提交次数264,360

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr)
            return false;
        if(isSameTree(root, subRoot);)
            return true;
        if(isSubtree(root->left,subRoot);)
            return true;
        if(isSubtree(root->right,subRoot);)
            return true;
        return false;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr)
            return true;
        if(!(p!=nullptr && q!=nullptr && p->val == q->val))
            return false;
        bool retl = isSameTree(p->left,q->left);
        if(retl == false)
            return false;
        bool retr = isSameTree(p->right,q->right);
        if(retr == false)
            return false;
        return true;
    }
};

判断一个树是不是另一个的子树,这里的解法仍然是前序遍历,思路就是遍历每一个非空结点,把这个结点看成某一个树的根节点,只是这些根节点或大或小而已,然后调用isSameTree函数判断两个树是否相同。思路还是那么一个思路,没什么两样。

给出个错误解法吧:

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr)
            return false;
        bool ret = isSameTree(root, subRoot);
        if(ret == true)
            return true;
        ret = isSameTree(root->left,subRoot);
        if(ret == true)
            return true;
        ret = isSameTree(root->right,subRoot);
        if(ret == true)
            return true;
        return false;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr)
            return true;
        if(!(p!=nullptr && q!=nullptr && p->val == q->val))
            return false;
        bool retl = isSameTree(p->left,q->left);
        if(retl == false)
            return false;
        bool retr = isSameTree(p->right,q->right);
        if(retr == false)
            return false;
        return true;
    }
};

这是起初写的错误解法,仔细想想还是容易理解的,34,不同,IsSameTree函数第二个if直接返回false,不会递归,然后进入3函数的左子树调用,仍然直接返回false,再走到3的右子树,也是直接返回false。并没有起到递归的作用。

小总结:

简单来说就是遍历了一遍, 你可以直接把这个对结点的操作忽略掉,然后只看左递归和右递归,你就会发现,这两个函数恰好遍历了一遍整个树,然后你可以在适当的位置写一些操作,就是对每个结点的操作,比如572这个题,就是比较两个树是否相等。

#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = new BTNode();
	assert(newnode);
	newnode->data = x;
	newnode->right = nullptr;
	newnode->left = nullptr;
	return newnode;
}
BTNode* CreateTree(string s, int* pi)
{
    if(s[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyNode(s[(*pi)++]);
    root->left = CreateTree(s, pi);
    root->right = CreateTree(s, pi);
    return root;
}
void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->left);
    cout<<root->data<<" ";
    InOrder(root->right);
}
int main()
{
    string s;
    cin >> s;
    int i = 0;
    BTNode* root = CreateTree(s, &i);
    InOrder(root);
    return 0;
}

这个题相对而言就有点新颖了,创建正确的树是关键。后面的中序遍历就是一些基本操作了。

有关根据给定字符串创建合适的二叉树:其实根本上还是一种前序遍历的思路,可以直接把这个字符串看作一个正确的二叉树,s和pi的结合可以逐个遍历每个字符,每次进入函数都会创建对应的结点。而遇到#则返回空结点,作为上一个结点的左子树或者右子树,并同时结束递归。。。。。

  • 销毁二叉树
void DestroyTree(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	// 后序销毁,先销毁左子树,再销毁右子树,最后销毁根节点,对于每一棵树都是这样的操作。
	DestroyTree(root->left);
	DestroyTree(root->right);
	delete root;
}

后序销毁。。

  • 层序遍历
// 层序遍历 利用队列
void LevelOrder(BTNode* root)
{
	queue<BTNode*> q;
	if (root != NULL)
	{
		q.push(root);
	}
	while (!q.empty())
	{
		BTNode* root = q.front();
		cout << root->data << " ";
		q.pop();
		if (root->left)
		{
			q.push(root->left);
		}
		if (root->right)
		{
			q.push(root->right);
		}
	}
	cout << endl;
}

利用队列,先将根节点插入队列,然后出根节点,进根节点的两个子节点,当然也有可能是一个个,也有可能只有一个根节点。 每次都是出一个结点,进这个结点的子节点。达到层序遍历的目的。

  • 利用层序遍历判断一颗二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	queue<BTNode*> q;
	if (root != NULL)
	{
		q.push(root);
	}
	while (!q.empty())
	{
		BTNode* root = q.front();
		q.pop();
		if (root)
		{
			q.push(root->left);
			q.push(root->right);
		}
		else
		{
			break;
		}
	}
	while (!q.empty())
	{
		if (q.front() != NULL)
			return false;
		q.pop();
	}
	return true;
}

完全二叉树的特点:层序遍历后,前方遍历的一定全是非空结点,后方一定全是空结点,利用这一特点进行判断。即:遇到空结点之后再判断队列中是否后续都是空结点。

到此这篇关于C语言进阶二叉树的基础与销毁及层序遍历详解的文章就介绍到这了,更多相关C语言二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言植物大战数据结构二叉树递归

    目录 前言 一.二叉树的遍历算法 1.构造二叉树 2.前序遍历(递归图是重点.) 3.中序遍历 4.后序遍历 二.二叉树遍历算法的应用 1.求节点个数 3.求第k层节点个数 4.查找值为x的节点 5.二叉树销毁 6.前序遍历构建二叉树 7.判断二叉树是否是完全二叉树 8.求二叉树的深度 三.二叉树LeetCode题目 1.单值二叉树 2. 检查两颗树是否相同 3. 对称二叉树 4.另一颗树的子树 6.反转二叉树 " 梧桐更兼细雨,到黄昏.点点滴滴." C语言朱武大战数据结构专栏 C语言

  • C语言二叉树层序遍历

    实现下面图中的二叉树层序遍历 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <unistd.h> typedef struct node { char data; struct node *lchild; struct node *rchild; }NODE, *PNODE; typedef struct qnode { PNODE pnode; struct qno

  • C语言近万字为你讲透树与二叉树

    目录 一.树概念及结构 1.1 树的概念 1.2 树的相关概念 1.3 树的表示 二.二叉树概念及结构 2.1 概念 2.2 特殊的二叉树: 2.3 二叉树的性质 2.4 二叉树的存储结构 1. 顺序存储 2. 链式存储 三.实现完全二叉树堆并实现堆排序 3.1 堆的概念和结构 3.2 实现堆的难点 3.3 小堆的实现 3.4 堆的应用-堆排序 四.Top-k问题 总结 一.树概念及结构 1.1 树的概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫

  • C语言进阶练习二叉树的递归遍历

    目录 二叉树的前中后序遍历 遍历二叉树求二叉树的结点个数 遍历二叉树求二叉树的叶子结点个数 求二叉树中data为x的结点 求二叉树的深度 二叉树的前中后序遍历 所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次.访问结点所做的操作依赖于具体的应用问题. 遍历 是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础. 按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历: 1. 前序遍历(Preorder Traversal

  • C语言植物大战数据结构二叉树堆

    目录 前言 堆的概念 创建结构体 初始化结构体 销毁结构体 向堆中插入数据 1.堆的物理结构和逻辑结构 2.完全二叉树下标规律 3.插入数据思路 依次打印堆的值 删除堆顶的值 判断堆是否为空 求堆中有几个元素 得到堆顶的值 堆排序 总体代码 Heap.h Heap.c Test.c “竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生” C语言朱武大战数据结构专栏 C语言植物大战数据结构快速排序图文示例 C语言植物大战数据结构希尔排序算法 C语言植物大战数据结构堆排序图文示例 C语言植物大战数据结构二叉树递归

  • C语言数据结构详细解析二叉树的操作

    目录 二叉树分类 二叉树性质 性质的使用 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历 求二叉树的节点数 求二叉树叶子结点个数 求二叉树的最大深度 二叉树的销毁 二叉树分类 满二叉树 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树.也可以理解为每一层的结点数都达到最大值的二叉树. 完全二叉树 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下.从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为

  • C语言线索二叉树基础解读

    目录 线索二叉树的意义 线索二叉树的定义 线索二叉树结构的实现 二叉树的线索存储结构 二叉树的中序线索化 线索二叉树的中序遍历 总结 线索二叉树的意义 对于一个有n个节点的二叉树,每个节点有指向左右孩子的指针域.其中会出现n+ 1个空指针域,这些空间不储存任何事物,浪费着内存的资源. 对于一些需要频繁进行二叉树遍历操作的场合,二叉树的非递归遍历操作过程相对比较复杂,递归遍历虽然简单明了,但是会有额外的开销,对于操作的时间和空间都比较浪费. 我们可以考虑利用这些空地址,存放指向节点在某种遍历次序下

  • C语言树与二叉树基础全刨析

    目录 一.树的概念和结构 1.1 树的概念 1.2 树的结构 & 相关名词解释 1.3 树的表示 1.4 树的应用 二.二叉树的概念 & 存储结构(重要) 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树的存储结构 一.树的概念和结构 1.1 树的概念 树是一种非线性的数据结构,它是由 n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 有一个特殊的结点,称为根结点,根节点没有前

  • C++超详细啊境界auto与nullptr的使用

    目录 一. auto关键字 1. auto介绍 2. 使用规则 3.auto不能推导的场景 二.基于范围的for循环(C++11) 1. 范围for的语法 2.范围for的使用条件 三. 指针空值nullptr(C++11) 一. auto关键字 1. auto介绍 在早期C/C++中auto的含义是:使用auto修饰的变量,是具有自动存储器的局部变量. 但是在C++11开始,赋予了auto全新的含义即:auto不再是一个存储类型指示符,而是作为一个新的类型指示符来指示编译器,auto声明的变量

  • C语言进阶二叉树的基础与销毁及层序遍历详解

    单值二叉树 难度简单 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树. 只有给定的树是单值二叉树时,才返回true:否则返回false. 示例 1: 输入:[1,1,1,1,1,null,1]输出:true 示例 2: 输入:[2,2,2,5,2]输出:false 提示: 给定树的节点数范围是[1, 100]. 每个节点的值都是整数,范围为[0, 99]. 解1: 最简单易懂的解法,先序遍历一遍,把每个节点都和那个根节点的val值相比.最后判断flag是否为真,若为假,则表明树中有

  • C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

  • Go语言基础设计模式之策略模式示例详解

    目录 概述 针对同一类型问题的多种处理方式 一.不使用策略模式 二.策略模式 UML 总结 示例 概述 定义一系列算法,将每个算法封装起来.并让它们能够相互替换.策略模式让算法独立于使用它的客户而变化. 针对同一类型问题的多种处理方式 一.不使用策略模式 package main import "fmt" type User struct { Name string } func (this User) travel(t string) { switch t { case "

  • Go语言基础函数基本用法及示例详解

    目录 概述 语法 函数定义 一.函数参数 无参数无返回 有参数有返回 函数值传递 函数引用传递 可变参数列表 无默认参数 函数作为参数 二.返回值 多个返回值 跳过返回值 匿名函数 匿名函数可以赋值给一个变量 为函数类型添加方法 总结 示例 概述 函数是基本的代码块,用于执行一个任务 语法 函数定义 func 函数名称( 参数列表] ) (返回值列表]){ 执行语句 } 一.函数参数 无参数无返回 func add() 有参数有返回 func add(a, b int) int 函数值传递 fu

  • Go语言基础go fmt命令使用示例详解

    go fmt 命令主要是用来帮你格式化所写好的代码文件[很多第三方集成软件都是使用了go fmt命令] 一.使用: go fmt <文件名>.go 使用go fmt命令,更多时候是用gofmt,而且需要参数 -w,否则格式化结果不会写入文件.gofmt -w src,可以格式化整个项目. 二.参数介绍 -l 显示那些需要格式化的文件 -w 把改写后的内容直接写入到文件中,而不是作为结果打印到标准输出. -r 添加形如"a[b:len(a)] -> a[b:]"的重写规

  • Go语言基础go install命令使用示例详解

    目录 go install 一.使用 二.包名和目录名的关系 三.注意 go install 编译并安装代码包,对于库,会生成目标库文件,并且放置到GOPATH/pgk目录下. 对于可执文件,会生成目标可执行文件,并且放置到GOPATH/bin目录下 一.使用 命令 描述 go install lib 编译安装package lib,会为main包在bin下生成可执行exe文件 go install lib2 lib/util 同时编译安装lib2和lib/util两个package. 二.包名

  • Go语言基础类型及常量用法示例详解

    目录 基础类型 概述 按类别有以下几种数据类型 数值类型 派生类型 变量 概述 单个变量声明 多个变量声明 基础类型 概述 在 Go 编程语言中,数据类型用于声明函数和变量.数据类型的出现时为了把数据分成所需要用大数据的时候才需要申请大内存,这样可以充分的列用内存. 按类别有以下几种数据类型 数值类型 布尔型 bool:布尔型的值只可以是常量 true 或者 false,默认值为 false. 字符串类型 string:编码统一为 UTF-8 编码标识 Unicode 文本,默认值为空字符串.

  • Go语言基础枚举的用法及示例详解

    目录 概述 一.普通枚举 二.自增枚举 注意 代码 概述 将变量的值一一列举出来,变量只限于列举出来的值的范围内取值 Go语言中没有枚举这种数据类型的,但是可以使用const配合iota模式来实现 一.普通枚举 const ( cpp = 0 java = 1 python = 2 golang = 3 ) 二.自增枚举 iota只能在常量的表达式中使用 fmt.Println(iota) //undefined: iota 它默认开始值是0,const中每增加一行加1 const ( a =

  • Go语言基础学习之数组的使用详解

    目录 1. Array(数组) 2. 声明数组 3. 数组初始化 3.1 方式一 3.2 方式二 3.3 方式三 3.4 多维数组 4. 遍历数组&取值 5. 数组拷贝和传参 数组相必大家都很熟悉,各大语言也都有数组的身影.Go 语言也提供了数组类型的数据结构. 1. Array(数组) 数组是同一种数据类型的固定长度的元素集合.在 Go 语言中,数组声明后长度就不能改变了,可以修改数组的元素,用法: // eg: 定义一个长度为 10 的 int 数组 var a [10]int 2. 声明数

  • C语言自定义数据类型的结构体、枚举和联合详解

    结构体基础知识 首先结构体的出现是因为我们使用C语言的基本类型无法满足我们的需求,比如我们要描述一本书,就需要书名,作者,价格,出版社等等一系列的属性,无疑C语言的基本数据类型无法解决,所以就出现了最重要的自定义数据类型,结构体. 首先我们创建一个书的结构体类型来认识一下 struct Book { char name[20]; char author[20]; int price; }; 首先是struct是结构体关键字,用来告诉编译器你这里声明的是一个结构体类型而不是其他的东西,然后是Boo

随机推荐