二叉树与堆-阿里云开发者社区

大家好，我是纪宁。

树是一种特殊的数据结构，也是我们的学习数据结构由线性转向非线性的试金石。所以弄懂树的结构及二叉树就非常重要。

这篇文章将重点介绍关于树的面试、笔试题中经常出现的二叉树和堆的问题。

1.树的概念及结构（先导知识，了解可跳过）

1.1 什么是树

要学习二叉树，首先要了解树这个数据结构的相关基础知识。

我们以前使用的这些数据结构像顺序表、链表、栈这些，都是属于线性的数据结构。而树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

线性数据结构

线性数据结构是一种按顺序组织和访问元素的数据结构，其中每个元素都有一个前驱和一个后继。线性结构可以视为一系列相同类型的数据元素的有序集合。常见的线性数据结构包括数组、链表、栈、队列等。在线性数据结构中，元素之间的关系是单向的，即只能从前往后或从后往前依次访问，不能跳跃式地访问。由于其简单性和高效性，线性数据结构在许多算法和程序中都得到广泛的应用。

非线性数据结构

非线性数据结构是指数据元素之间存在非简单的层次关系，即数据元素之间不是一对一的关系，而是一对多或多对多的关系。常见的非线性数据结构有树、图等。

树的应用有文件系统、数据库索引、哈希表、堆、图、决策树、神经网络等

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的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

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 ,则有n0=n1+1
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= . (ps：是log以2为底，n+1为对数)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.5 二叉树的存储结构（重点）

2.5.1 二叉树的顺序存储

二叉树的顺序存储是将树节点按照层次顺序存储在数组中。根节点存储在数组下标为 1 的位置处，左子树节点存储在数组下标为 2k 的位置处，右子树节点存储在数组下标为 2k+1 的位置处。

从上图可以看出，非完全二叉树用数组存储会导致大量的空间浪费，所以顺序存储只适合于完全二叉树。我们通常把堆这种特殊的二叉树使用数组来顺序存储。

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 == 0，o下标处的数据为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 (child>0)
  {
    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 (child>0)
  {
    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 (end>0)
  {
    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 NULL;
  }
  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(root==NULL){
    return true;
  }
  if(root->left!=NULL&&root->left->val!=root->val){
    return false;
  }
  if(root->right!=NULL&&root->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(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);
}

p == NULL && q ==NULL 可以保证当两个空结点返回 true；p = = NULL || q = = NULL 放后面可以保证在两个结点都不是 NULL 的情况下，如果有一个结点为 NULL ，而另一个结点不为NULL的时候返回 false；在递归里只要有一个 false ，程序就会返回 fasle 。当遍历结束后，所有返回都是 true ，程序才会返回 true。

对称二叉树

题目来源于 leetcode ：对称二叉树

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

bool check(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 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(root==NULL){
        return 0;
    }
    return 1+TreeCount(root->left)+TreeCount(root->right);
}
void PrevOrder(struct TreeNode*root,int*i,int*a){
    if(root==NULL){
        return;
    }
    a[(*i)++]=root->val;
    PrevOrder(root->left,i,a);
    PrevOrder(root->right,i,a);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int count=TreeCount(root);
    *returnSize=count;
    int*a=(int*)malloc(sizeof(int)*count);
    int i=0;
    PrevOrder(root,&i,a);
    return a;
}

二叉树的中序遍历

题目来源于 Leetcode ：二叉树的中序遍历

思路与前序遍历相同，将顺序改为先左再中再右。

nt TreeCount(struct TreeNode*root){
    if(root==NULL){
        return 0;
    }
    return 1+TreeCount(root->left)+TreeCount(root->right);
}
void InOrder(struct TreeNode*root,int*i,int*a){
    if(root==NULL){
        return;
    }
    InOrder(root->left,i,a);
    a[(*i)++]=root->val;
    InOrder(root->right,i,a);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeCount(root);
    int*a=(int*)malloc(sizeof(int)*n);  
    int i=0;
    InOrder(root,&i,a);
    *returnSize=n;
    return a;
}

二叉树的后序遍历

题目来源于leetcode：二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

思路与前面两种遍历一样。

int TreeCount(struct TreeNode*root){
    if(root==NULL){
        return 0;
    }
    return 1+TreeCount(root->left)+TreeCount(root->right);
}
void PostOrder(struct TreeNode*root,int*i,int*a){
    if(root==NULL){
        return;
    }
    PostOrder(root->left,i,a);
    PostOrder(root->right,i,a);
    a[(*i)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeCount(root);
    int*a=(int*)malloc(sizeof(int)*n);
    int i=0;
    PostOrder(root,&i,a);
    *returnSize=n;
    return a;
}

另一个树的子树

题目来源于leetcode：另一个树的子树

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

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

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;
  }
  if(root->val==subRoot->val){
    if(isSameTree(root,subRoot)){
      return true;
    }
  }
  return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

这道题目其实是判断两个树是否是同一棵的加强版，只需要在判断出两个结点相同的时候，进而判断这个结点对用的子树是否与题目给出的树为同一棵树即可。

🚀🚀兄弟们，顶峰相见！💪

二叉树与堆

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练习

单值二叉树

检查两棵树是否相同

对称二叉树

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

另一个树的子树

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

二叉树与堆

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练习

单值二叉树

检查两棵树是否相同

对称二叉树

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

另一个树的子树

热门文章

最新文章

相关电子书