天津雍鑫建设投资集团网站,wordpress站内跳转,建e网手机版,建设通网站是免费的吗文章目录 1.树的概念及结构#xff08;先导知识#xff0c;了解可跳过#xff09;1.1 什么是树1.2 树的相关概念1.3 普通树的存储结构结点的定义 2.二叉树2.1 概念2.2 现实中的二叉树2.3 特殊的二叉树2.4 二叉树的性质#xff08;笔试选择题常见#xff09;2.5 二叉树的存… 文章目录 1.树的概念及结构先导知识了解可跳过1.1 什么是树1.2 树的相关概念1.3 普通树的存储结构结点的定义 2.二叉树2.1 概念2.2 现实中的二叉树2.3 特殊的二叉树2.4 二叉树的性质笔试选择题常见2.5 二叉树的存储结构重点2.5.1 二叉树的顺序存储2.5.1.1 堆——特殊的完全二叉树堆的插入、删除及堆排序堆的向上调整算法及代码讲解堆的向下调整算法及代码讲解堆排序 2.5.1.2 堆的应用——TopK问题 2.5.2 二叉树的链式存储2.5.3 二叉树基础OJ练习单值二叉树检查两棵树是否相同对称二叉树二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历另一个树的子树 大家好我是纪宁。 树是一种特殊的数据结构也是我们的学习数据结构由线性转向非线性的试金石。所以弄懂树的结构及二叉树就非常重要。 这篇文章将重点介绍关于树的面试、笔试题中经常出现的二叉树和堆的问题。 1.树的概念及结构先导知识了解可跳过
1.1 什么是树
要学习二叉树首先要了解树这个数据结构的相关基础知识。 我们以前使用的这些数据结构像顺序表、链表、栈这些都是属于线性的数据结构。而树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 线性数据结构 线性数据结构是一种按顺序组织和访问元素的数据结构其中每个元素都有一个前驱和一个后继。线性结构可以视为一系列相同类型的数据元素的有序集合。常见的线性数据结构包括数组、链表、栈、队列等。在线性数据结构中元素之间的关系是单向的即只能从前往后或从后往前依次访问不能跳跃式地访问。由于其简单性和高效性线性数据结构在许多算法和程序中都得到广泛的应用。 非线性数据结构 非线性数据结构是指数据元素之间存在非简单的层次关系即数据元素之间不是一对一的关系而是一对多或多对多的关系。常见的非线性数据结构有树、图等。 树的应用有文件系统、数据库索引、哈希表、堆、图、决策树、神经网络等
1.2 树的相关概念 下面所有概念的介绍将使用上面的树 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林
1.3 普通树的存储结构
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 孩子兄弟表示法 孩子兄弟表示法是一种树状结构的数据表示方式。它通过将每个节点表示为一个记录并以指针形式链接各个节点来表达树形结构。在孩子兄弟表示法中每个节点包含一个指向它第一个孩子节点的指针和一个指向它下一个兄弟节点的指针。如果一个节点没有孩子或者兄弟节点那么对应指针值就为NULL。这种表示法常用于表示树和森林等数据结构。 结点的定义
typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};这种结构实现方法简称为左孩子右兄弟
2.二叉树
2.1 概念
二叉树是一种特殊的树一个二叉树由根节点和左右子树组成。左右子树也都由多个结点组成且每个结点最多只有两个子节点。二叉树有有序树所以左右结点/子树的次序不能颠倒。
2.2 现实中的二叉树 二结点的深度每个节点的深度是指它到根节点的距离即根节点的深度为0 结点的高度指从该节点到叶子节点的最长路径即叶子节点的高度为0二叉树的高度等于它的根节点的高度。
2.3 特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
2.4 二叉树的性质笔试选择题常见
若规定根节点的层数为1则一棵非空二叉树的第i层上最多有 个结点.若规定根节点的层数为1则深度为h的二叉树的最大结点数是 .对任何一棵二叉树, 如果度为0其叶结点个数为n0 度为2的分支结点个数为n1 ,则有n0n11若规定根节点的层数为1具有n个结点的满二叉树的深度h . (ps 是log以2为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 若2i1n左孩子序号2i12i1n否则无左孩子 若2i2n右孩子序号2i22i2n否则无右孩子
2.5 二叉树的存储结构重点
2.5.1 二叉树的顺序存储
二叉树的顺序存储是将树节点按照层次顺序存储在数组中。根节点存储在数组下标为 1 的位置处左子树节点存储在数组下标为 2k 的位置处右子树节点存储在数组下标为 2k1 的位置处。 从上图可以看出非完全二叉树用数组存储会导致大量的空间浪费所以顺序存储只适合于完全二叉树。我们通常把堆这种特殊的二叉树使用数组来顺序存储。
2.5.1.1 堆——特殊的完全二叉树 堆的定义 堆Heap是一种特殊的树形数据结构在堆中父节点的值总是大于或小于其子节点的值且堆总是一棵完全二叉树。根节点最大的堆叫做大根堆根节点最小的堆叫做小根堆。 堆的插入、删除及堆排序
当我们将完全二叉树或者满二叉树的数据按顺序存储在数组中的时候因为他们有一定的对应关系所以可以通过公式由双亲结点的下标计算出并找到子节点的下标由子节点的下标计算并找到出对应双亲结点的下标。 二叉树索引公式 leftchild 2 * parent 1 rightchild 2 * parent 2 parent (child - 1)/2 当我们将堆存储在数组中的时候如果还想要往堆中添加数据可以使用堆的向上调整算法和向下调整算法这两种方法的使用前提要插入位置的前面或后面的数据是堆。
堆的向上调整算法及代码讲解
当我们要往一个堆中添加数据的时候首先拿到的肯定是你要添加的数据和数据被添加位置的下标通过这个下标可以计算出它双亲结点父节点的下标这个数据与它的双亲结点进行比较如果相对大小不符合大堆或者小堆的要求它就与双亲结点交换位置。现在假设它和双亲结点交换了位置那么这个数据就获得了新的下标通过这个下标可以计算出它的新双亲结点的位置再次进行比较如此往复直至比较到根节点为止。 比如我现在要在下面的小堆中插入 0 这个数据但不能改变小堆的性质父节点 子节点就可以采用堆的向上调整算法。 0 刚插入时的下标是 6可以计算出它的父节点下标为(6 - 1)/2 2 通过下标索引可以得出它的父节点为 4在小堆中父节点要小于子节点所以他俩要交换位置如图 这时它0的下标就变为了 2通过计算它的父节点为(2-1)/2 0o下标处的数据为1,1大于0不符合小堆性质所以他俩要继续交换位置如图 如此就实现了将一个数据插入到一个小堆中且时间复杂度为 O(logN) 代码讲解
void swap(HPDataType* parent, HPDataType* child)
{int tmp *parent;*parent *child;*child tmp;
}
void Adjustup(HPDataType* a, int child)//建小堆,将插进来的值往上调整
{assert(a);int parent (child - 1) / 2;while (child0){if (a[parent] a[child]){swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else{break;}}
}这段代码有几个需要注意的点swap函数传参的时候必须传地址这样才能通过形参解引用达到改变实参的目的循环的终止条件是 child 0或者当前情况符合预期即当 child 一直调整到根节点或者已经符合小堆/大堆的性质的时候就停止循环那么此时在堆里插入数据的操作已经完成。 当我们有一组杂乱的数据并且没有任何堆结构的时候也可以使用向上调整来建堆达到堆排序后文有详细的效果。 int arr[] { 10,1,9,2,9,767,32,17,78,79,69 };int sz sizeof(arr) / sizeof(arr[0]);for (int i 1; i sz; i){Adjustup(arr, i);//建小堆}代码讲解 这段代码从下标为1开始向上调整建堆相当于先将 arr[0] 放入堆中然后从第二个数据开始逐个向上调整只到将所有数据都调整完堆就建好了因为要数组有N个元素每次向上调整的时间复杂度为O(logN)所以这种逐个向上调整建堆的时间复杂度为 O(N*logN)
堆的向下调整算法及代码讲解
当我们想要删除堆顶元素的时候大多情况下会使用堆的向下调整算法。 例如现在要在不改变小堆性质的情况下删除一个小堆的堆顶元素这时候初学者可能会有这样的想法直接将数组的第一个数据删除然后数据整体向前移动。这种操作其实就是当时顺序表所做的头删但顺序表是线性结构直接头删不影响其他元素但二叉树是非线性结构直接删会破坏数据之间原来的逻辑关系比如父子之间的下标对应关系小堆的性质等都会被破坏。 如图要删除堆顶的 2如果采用直接删除整体前移的方式剩下的数据已经不再是一个小堆了它的小堆性质已经被破坏了。所以要想一个新的方法来解决堆顶删除数据的问题。 解决方法 先将堆顶元素与最后一个元素交换位置再删除数组尾元素这个尾元素就是刚换过去的堆顶元素然后使用向下调整算法从堆顶对数组进行调整。 堆的向下调整算法 向下调整的过程是从堆的某个节点开始将其与其子节点进行比较并交换位置直到该节点与其子节点的大小关系符合堆的性质。 假设现在就要将上面初步调整后的数组调整为小堆从根节点开始调整因为堆发生改变的地方就是根节点比较根节点 8 与它左右结点的值并找到它孩子结点中最小的结点 3 这样可以保证8 与 它交换位置后树的前两层符合小堆的性质调整一步后的结果如图此时要调整的结点就变成了 8 这个位置的结点。 继续对8位置处的结点进行向下调整找到8的左右结点中最小的那一个与这个结点交换位置交换后它已经没有子节点了并且父节点也小于 8循环结束。这时候堆的向下调整就完毕了时间复杂度为 O(logN) 代码讲解
void Adjustdown(HPDataType* a, int size, int parent)//小堆
{assert(a);int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child ;}if (a[parent] a[child]){swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}向下调整算法需要将数组首元素地址数组元素个数及要进行调整的初始下标传进来。因为是向下调整所以这个出示下表就是相对的父节点通过这个下标可以计算出它左右孩子结点的位置可以假设左孩子就是两个孩子中最小的那一个如果右孩子比左孩子小的话就将孩子的下标加1。 然后就是看它和它孩子的关系是否符合小堆的性质如果符合就直接中止循环如果不符合就与孩子交换位置后再次循环进行判断直到它的孩子在下标数值上已经越界或者符合小堆性质了就结束循环向下调整建堆完成。
堆排序
堆排序是一种效率比较高的算法时间复杂度为O(N*logN)那么它是如何实现的呢 堆排序顾名思义就是利用堆进行排序当我们拿到一组杂乱的数据时如果想使用堆排序首先先要对这组数据进行建堆可以采用向上调整或向下调整建堆。第二步就是如何进行排序了。 当要对这组数据进行升序排列时通常要建立一个大堆要进行降序排列时通常要建立小堆。 例如现在要对一组数据进行降序排列那么就要建立一个小堆因为小堆的父节点总是小于子节点所以堆顶元素一定就是最小的元素。将堆顶元素与最后一个元素交换位置后即相当于最小的元素被 ‘排’ 到了最后面然后从堆顶开始向下调整调整可以保证除了末尾元素其余元素均遵循小堆的性质。 那么调整结束后根据小堆性质这n-1个数中最小的元素也就是整个数组中第二小的元素就被调整到了堆顶的位置将它再与堆的最后一个元素数组的倒数第二个元素进行交换…一直循环直到将所有的元素都排好序。 有N个元素每个元素调整的时间复杂度为O(logN)所以整体的时间复杂度为 O(N * logN)
void Adjustup(HPDataType* a, int child)//建小堆,将插进来的值往上调整
{assert(a);int parent (child - 1) / 2;while (child0){if (a[parent] a[child]){swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else{break;}}
}
void Adjustdown(HPDataType* a, int size, int parent)//小堆
{assert(a);int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child ;}if (a[parent] a[child]){swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(HPDataType* a, int n)
{for (int i 1; i n; i){Adjustup(a, i);//建小堆}int end n - 1;while (end0){swap(a[0], a[end]);end--;Adjustdown(a, n, 0);}
}2.5.1.2 堆的应用——TopK问题
假设现在有100亿甚至更多个数据如何最快找出其中最大的 k 个数据这就是著名的TopK问题。 如果使用其他的方法这么多数据确实排非常非常复杂可如果使用堆排序的思想就可以很好的解决这个问题。 先录入待排序文件中的前100个数据并建立小堆。再依次取剩余的元素和堆顶元素进行比较如果大于堆顶元素就替换入堆然后向下调整可以保证堆顶一直是最小的元素。 当将100亿个数据全部比较并调整依次后那么堆中剩余的数据就是这100亿个数据中最大的100个数据。使用这种方式排序时间复杂度是 O(N*logK)算是非常高了
2.5.2 二叉树的链式存储
二叉树的链式结构常适用于非完全二叉树的情况并且对链式二叉树结构对空间的利用率高删除、插入更加方便高效。树中的父子关系也只需要使用指针进行维护即可。 二叉树链式结构每个结点包括两个指针域和一个数据域指针域分别指向左孩子和右孩子数据域存储的是结点的数据。 链式二叉树的很多问题比较适合使用递归来解决递归的原理则是函数栈帧的创建和销毁。这个知识点不清楚的读者可以去看博主的这篇文章 从汇编代码探究函数栈帧的创建和销毁的底层原理 结点结构的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;
}BTNode;新节点的创建
BTNode* BuyNode(int x)
{BTNode* nownode (BTNode*)malloc(sizeof(BTNode));nownode-left NULL;nownode-right NULL;nownode-val x;return nownode;
}需要构造什么样的二叉树就手动控制他们的结点指向。例如要构造下图所示的二叉树 构造一颗二叉树
int main()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;
}链式二叉树的三种遍历 先序遍历先输出根结点再按照先序遍历左子树再按照先序遍历右子树的顺序遍历整棵二叉树。 中序遍历按照中序遍历左子树的顺序遍历再输出根结点最后按照中序遍历右子树的顺序遍历整棵二叉树。 后序遍历按照后序遍历左子树的顺序遍历再按照后序遍历右子树的顺序遍历最后输出根结点。 先序遍历
void PrevOrder(BTNode* node){if (node NULL){printf(N );return;}printf(%d , node-val);PrevOrder(node-left);PrevOrder(node-right);
}输出结果 光看代码递归很是晦涩难懂这里给大家推荐一种可以快速理解的方式画递归展开图 就以二叉树的前序遍历的左子树递归举例子 右子树的递归也是同样的道理。 中序遍历
void InOrder(BTNode* node)
{if (node NULL){printf(N );return;}InOrder(node-left);printf(%d , node-val);InOrder(node-right);
}后序遍历
void PostOrder(BTNode*node)
{if (node NULL){printf(N );return;}PostOrder(node-left);PostOrder(node-right);printf(%d , node-val);
}二叉树的层序遍历 二叉树的层序遍历用了队列部分的知识。先将链式二叉树的第一个结点入队列队列的数据域要为可以存储二叉树结点类型的指针然后依靠这个结点进行遍历先将队列中第一个结点的的左右结点按顺序入队列再将第一个结点 pop 掉一直到遍历完所有结点为止循环条件中止条件也就是队列为空。
void LeverOrder(BTNode* root)
{Que que;QueueInit(que);if (root ! NULL){QueuePush(que, root);}while (!QueueEmpty(que)){BTNode* front QueueFront(que);printf(%d , front-val);if (front-left ! NULL){QueuePush(que, front-left);}if (front-right ! NULL){QueuePush(que, front-right);}QueuePop(que);}QueueDestroy(que);
}计算二叉树结点的个数
int TreeSize(BTNode* node)//结点个数
{if (node NULL){return 0;}return 1 TreeSize(node-left) TreeSize(node-right);
}计算二叉树叶子结点的个数
int TreeLeafSzie(BTNode* node)//叶子结点个数
{if (node NULL){return 0;}if (node-left NULL node-right NULL){return 1;}return TreeLeafSzie(node-left) TreeLeafSzie(node-right);
}二叉树第k层结点的个数
int TreeKLeaf(BTNode* node, int k)//第k层的结点个数
{if (node NULL){return 0;}if (k 1){return 1;}return TreeKLeaf(node-left, k - 1) TreeKLeaf(node-right, k - 1);
}查找值为x的结点
// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, int x)
{if (root NULL){return;}if (root-val x){return root;}if (TreeFind(root-left, x) ! NULL)return TreeFind(root-left, x);if (TreeFind(root-right, x) ! NULL)return TreeFind(root-right, x);return NULL;
}二叉树的销毁
void TreeDestroy(BTNode* root)
{if (root NULL){return;}TreeDestroy(root-left);TreeDestroy(root-right);free(root);//root NULL;//写在函数调用的外面
}2.5.3 二叉树基础OJ练习
本模块OJ题目基本都是采用递归的思想。
单值二叉树
题目来源于 leetcode单值二叉树
如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时才返回 true否则返回 false。
bool isUnivalTree(struct TreeNode* root){if(rootNULL){return true;}if(root-left!NULLroot-left-val!root-val){return false;}if(root-right!NULLroot-right-val!root-val){return false;}return isUnivalTree(root-left)isUnivalTree(root-right);//层层递归往上走都是ture 最后才能过
}只要不符合就返回 false有一个 false 就没法过。一直进行递归直到所有的逻辑都为 true 时才会返回 true。还有需要注意的一点是在解引用-的时候必须保证指针不为空否则就会导致程序崩溃。
检查两棵树是否相同
题目来源于 leetcode检查两棵树是否相同
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL){return true;}if(pNULL||qNULL){return false;}if(p-val!q-val){return false;}return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}p NULL q NULL 可以保证当两个空结点返回 truep NULL || q NULL 放后面可以保证在两个结点都不是 NULL 的情况下如果有一个结点为 NULL 而另一个结点不为NULL的时候返回 false在递归里只要有一个 false 程序就会返回 fasle 。当遍历结束后所有返回都是 true 程序才会返回 true。
对称二叉树
题目来源于 leetcode 对称二叉树 给你一个二叉树的根节点 root 检查它是否轴对称。
bool check(struct TreeNode*p,struct TreeNode*q)
{if(pNULLqNULL){return true;}if(pNULL||qNULL){return false;}if(p-val!q-val){return false;}return check(p-left,q-right)check(p-right,q-left);
}
bool isSymmetric(struct TreeNode* root){return check(root,root);
}这道题和上一题的思路一样实现一个递归函数 通过同步相对方向移动这两个指针的方法来遍历这棵树p 指针和 q 指针一开始都指向这棵树的根随后 p 右移时q 左移p 左移时q 右移。每次检查当前 p 和 q 节点的值是否相等如果相等再判断左右子树是否对称。
二叉树的前序遍历
题目来源于 leetcode 二叉树的前序遍历
给你二叉树的根节点 root 返回它节点值的 前序 遍历。 这道题与实现二叉树链式结构时候基础操作的前序遍历函数一样不同的是这道题中需要用一个数组来存储每个结点的内容要在函数里对数组的索引序号进行持续修改就要将下标的地址作为参数传进去在函数里解引用改下标。
int TreeCount(struct TreeNode*root){if(rootNULL){return 0;}return 1TreeCount(root-left)TreeCount(root-right);
}
void PrevOrder(struct TreeNode*root,int*i,int*a){if(rootNULL){return;}a[(*i)]root-val;PrevOrder(root-left,i,a);PrevOrder(root-right,i,a);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){int countTreeCount(root);*returnSizecount;int*a(int*)malloc(sizeof(int)*count);int i0;PrevOrder(root,i,a);return a;
}二叉树的中序遍历
题目来源于 Leetcode 二叉树的中序遍历 思路与前序遍历相同将顺序改为先左再中再右。
nt TreeCount(struct TreeNode*root){if(rootNULL){return 0;}return 1TreeCount(root-left)TreeCount(root-right);
}
void InOrder(struct TreeNode*root,int*i,int*a){if(rootNULL){return;}InOrder(root-left,i,a);a[(*i)]root-val;InOrder(root-right,i,a);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){int nTreeCount(root);int*a(int*)malloc(sizeof(int)*n); int i0;InOrder(root,i,a);*returnSizen;return a;
}二叉树的后序遍历
题目来源于leetcode二叉树的后序遍历 给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 思路与前面两种遍历一样。
int TreeCount(struct TreeNode*root){if(rootNULL){return 0;}return 1TreeCount(root-left)TreeCount(root-right);
}
void PostOrder(struct TreeNode*root,int*i,int*a){if(rootNULL){return;}PostOrder(root-left,i,a);PostOrder(root-right,i,a);a[(*i)]root-val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){int nTreeCount(root);int*a(int*)malloc(sizeof(int)*n);int i0;PostOrder(root,i,a);*returnSizen;return a;
}另一个树的子树
题目来源于leetcode另一个树的子树 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL){return true;}if(pNULL||qNULL){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(rootNULL){return false;}if(root-valsubRoot-val){if(isSameTree(root,subRoot)){return true;}}return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}这道题目其实是判断两个树是否是同一棵的加强版只需要在判断出两个结点相同的时候进而判断这个结点对用的子树是否与题目给出的树为同一棵树即可。
兄弟们顶峰相见
