JackCin's blog
JackCin
2023-09-13
目录

二叉树(上)

# 二叉树

代码随想录 (programmercarl.com) (opens new window)

# 一、二叉树理论基础

二叉树大纲

# 1、二叉树的种类

# 1.1、满二叉树

  • 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

  • 如图所示：

img

  • 这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

# 1.2、完全二叉树

  • 什么是完全二叉树？

  • 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

大家要自己看完全二叉树的定义，很多同学对完全二叉树其实不是真正的懂了。

我来举一个典型的例子如题：

img

# 1.3、二叉搜索树

  • 前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

    • 它的左、右子树也分别为二叉排序树

  • 下面这两棵树都是搜索树

img

# 1.4、平衡二叉搜索树

  • 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树 或 它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

    如图：

img

  • 最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

  • C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

  • 所以大家使用自己熟悉的编程语言写算法，一定要知道常用的容器底层都是如何实现的，最基本的就是map、set等等，否则自己写的代码，自己对其性能分析都分析不清楚！

# 2、二叉树的存储方式

  • 二叉树可以链式存储，也可以顺序存储。

  • 那么链式存储方式就用指针， 顺序存储的方式就是用数组。

  • 顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

  • 链式存储如图：

img

  • 链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？

  • 其实就是用数组来存储二叉树，顺序存储的方式如图：

img

  • 用数组来存储二叉树如何遍历的呢？

    • 如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

  • 但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

  • 所以大家要了解，用数组依然可以表示二叉树。

# 3、二叉树的遍历方式

  • 二叉树主要有两种遍历方式：

    1. 深度优先遍历：先往深走，遇到叶子节点再往回走。

    2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）
  • 在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。

  • 看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

    • 前序遍历：中左右

    • 中序遍历：左中右

    • 后序遍历：左右中

大家可以对着如下图，看看自己理解的前后中序有没有问题。

img

  • 最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

  • 之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

  • 而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

  • 这里其实我们又了解了栈与队列的一个应用场景了。

  • 具体的实现我们后面都会讲的，这里大家先要清楚这些理论基础。

# 4、二叉树的定义

  • 刚刚我们说过了二叉树有两种存储方式顺序存储，顺序存储和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。

  • C++代码如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1
2
3
4
5
6

  • 大家会发现二叉树的定义 和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。

  • 这里要提醒大家要注意二叉树节点定义的书写方式。

  • 在现场面试的时候 面试官可能要求手写代码，所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。

  • 因为我们在刷leetcode的时候，节点的定义默认都定义好了，真到面试的时候，需要自己写节点定义的时候，有时候会一脸懵逼！

# 5、总结

  • 二叉树是一种基础数据结构，在算法面试中都是常客，也是众多数据结构的基石。

  • 本篇我们介绍了二叉树的种类、存储方式、遍历方式以及定义，比较全面的介绍了二叉树各个方面的重点，帮助大家扫一遍基础。

  • 说到二叉树，就不得不说递归，很多同学对递归都是又熟悉又陌生，递归的代码一般很简短，但每次都是一看就会，一写就废。

# 二、二叉树的递归遍历

  • 递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

  • 每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

    1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

    2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

    3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

  • 好了，我们确认了递归的三要素，接下来就来练练手：

  • 以下以前序遍历为例（用的C语言）：

      1. 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入数组来放节点的数值，（因为这里是c语言的写法，所以还需要传入数组长度），所以递归函数返回类型就是void，代码如下：
      void preOrder(struct TreeNode* root,int* ret ,int * returnSize)
      1
      1. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
      if(root == NULL) return;
      1
      1. 确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，（c语言还要给出 returnSize 的值）代码如下：
      ret[(*returnSize)++] = root ->val;
preOrder(root -> left,  ret , returnSize);
preOrder(root -> right, ret , returnSize);
      1
      2
      3
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
1
2
3
4
5
6
7
8
  • 单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

# 1、前序遍历

//前序遍历：
void preOrder(struct TreeNode* root, int* returnSize ,int* ret){
    if(root == NULL ){
        return;
    }
    ret[(*returnSize)++] = root ->val;
    preOrder(root->left,returnSize,ret);
    preOrder(root->right,returnSize,ret);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret =(int*)malloc(sizeof(int) * 100); //题目给出了树中节点数量的范围
    * returnSize =0;
    preOrder(root,returnSize,ret);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 2、中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void inOrder(struct TreeNode* root,int* ret,int* returnSize)
{
    if(root == NULL){
        return ;
    }
    inOrder(root -> left,ret,returnSize);
    ret[(*returnSize)++] = root->val;
    inOrder(root -> right,ret,returnSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*) malloc(sizeof(int)* 100);
    *returnSize = 0;
    inOrder(root,ret,returnSize);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 3、后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void postOrder(struct TreeNode* root,int* ret,int *returnSize){
    if(root == NULL){
        return ;
    }
    postOrder(root->left,ret,returnSize);
    postOrder(root->right,ret,returnSize);
    ret[(*returnSize)++] = root ->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int)* 100);
    * returnSize =0;
    postOrder(root,ret,returnSize);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 三、二叉树的迭代遍历

# 1、前序遍历

  • 前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
  • 为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

二叉树前序遍历（迭代法）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
1
2
3
4
5
6
7
8
9
10
11

# 1.1随想录写法

//随想录迭代写法
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res =(int*)malloc(sizeof(int) * 101); //题目给出了树中节点数量的范围
    * returnSize =0;
    if(root == NULL){
        return res;
    }
    
    struct TreeNode* stack[101];
    struct TreeNode* node;
    int top = 0;
    stack[top++] = root;
    

    while(top>0)
    {
        //出栈并保存到临时节点node，然后赋值给结果数组
        node = stack[--top];  
        res[(*returnSize)++] = node->val; 

        //之所以是先判断右节点是因为，我们是在出栈后才放进结果数组，栈又是先进后出，所以要先判断右节点
        
        //判断给出出栈的元素是否有右节点，有就入栈
        if(node ->right !=NULL) 
        {
            stack[top] = node ->right;
            top++;
        }
        //判断给出出栈的元素是否有左节点，有就入栈
        if(node->left !=NULL)  
        {
            stack[top] = node->left;
            top++;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 2.2迭代写法2


int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res =(int*)malloc(sizeof(int) * 101); //题目给出了树中节点数量的范围
    * returnSize =0;
    if(root == NULL){
        return res;
    }
    
    struct TreeNode* stack[101];
    struct TreeNode* node = root;
    int top=0;
    while(top>0 || node != NULL){
        while(node != NULL){
            res[(*returnSize)++] = node ->val;
            stack[top++] = node;
            node = node->left;
        }
        node = stack[--top]; 
        node = node -> right;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 2、中序遍历

  • 中序遍历不能像前序遍历(1.1)这种思路来写，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

  • 那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

    那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

    动画如下：

    二叉树中序遍历（迭代法）

  • 一层一层遍历左节点，直到找到最左，就开始处理节点，先将节点出栈，并赋值给结果数组，同时临时保存该节点，然后判断这个节点是否有右节点（node = node -> right，因为循环里if语句判断条件就是node是否为NULL,所以node指向node的右指针之后再循环就相当于判断）【之所以要出栈后再修改node指针，是因为我们出栈后就直接赋给结果数组，如果我们先修改，那么处理的节点就变了】，这样我们就实现了对每个节点判断是否存在不为空的子结点，(这段注释写的有点乱，最好画图，解结合上图理解)

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*) malloc(sizeof(int)* 100);
    *returnSize = 0;

    struct TreeNode* stack[101];
    struct TreeNode * node = root;
    int top=0;
    while( top > 0 || node != NULL ){
        //一直找到最左边
        if( node != NULL){
            stack[top++] = node;
            node = node->left;
        }
        //出现了NULL节点，就说明到了最左了，就弹出，并赋值，再判断其是否右右节点
        else {
            node = stack[--top];
            ret[(*returnSize)++] = node -> val;
            node = node -> right;
        }
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 这是和前序遍历（2.2）一样的写法

# 3、后序遍历

  • 再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

前序到后序

# 1.1随想录写法

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int)* 101);
    * returnSize =0;
    if( root == NULL){
        return ret;
    }
    struct TreeNode * node;
    struct TreeNode* stack[101];
    int top=0;
    stack[top++] =root;

    while(top > 0){
        //出栈并保存节点，再将节点数据赋给结果数组
       node = stack[--top];
       ret[(*returnSize)++] = node ->val;
       //判断是否有左节点，有就入栈
       if(node->left != NULL){
           stack[top] = node ->left;
           top++;
       }
       //判断是否有右节点，有就入栈
       if(node ->right != NULL){
           stack[top]= node->right;
           top++;
       }
    }
    //翻转数组
    int left=0,right= (*returnSize -1);
    while(left < right){
        int temp = ret[right];
        ret[right--] = ret[left];c
        ret[left++] = temp; 
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 1.2 迭代法2

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int)* 101);
    * returnSize =0;
    if( root == NULL){
        return ret;
    }
    struct TreeNode * node =root;
    struct TreeNode* stack[101];
    int top=0;
    while(top > 0 || node != NULL){
        while(node != NULL){
            ret[(*returnSize)++] = node ->val;
            stack[top++] = node;
            node = node->right;
        }
        node = stack[--top];
        node = node ->left;
    }
    //翻转数组
    int left=0,right= (*returnSize -1);
    while(left < right){
        int temp = ret[right];
        ret[right--] = ret[left];
        ret[left++] = temp; 
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 四、二叉树的统一迭代法

三里的迭代法，三种遍历的写法不同意，写起来比较麻烦，所以有没有什么迭代的写法可以统一的呢？

  • 答案肯定是有！
  • 我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！ (opens new window) (opens new window)中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
  • 那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
  • 如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

# 1、思路

  • 简单来讲就是，按我们想的遍历顺序反向将元素压入栈中（因为栈是先进后出），同时给需要处理的数据后压入一个NULL作为标志，这样就实现了对遍历元素和处理元素的不同处理
  • 仔细看下面代码，会发现3种遍历的写法左右几句代码的顺序改变了而已

# 2、步骤

    1. 创建结果数组和栈，同时将 root 压入栈中
    2. 循环判断栈是否为空，若为空，则返回结果数组result
      • 每次循环都先将栈顶元素赋给临时节点 node
      • 判断 node 是否为 NULL，若不是，则弹出栈顶元素，然后按我们想要遍历的顺序反序压将元素压入栈中（压入node对应的节点时，需要在其后压入NULL，用来标志其为操作元素）
      • 若node 为 NULL，则弹出栈顶的 NULL ，然后弹出之后的栈顶元素并赋值给结果数组

# 3、前序遍历

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res =(int*)malloc(sizeof(int) * 101); //题目给出了树中节点数量的范围
    * returnSize =0;
    if(root == NULL){
        return res;
    }
    
    struct TreeNode* stack[101];
    struct TreeNode* node;
    int top = 0;
    stack[top++] = root;
    
    while(top>0)
    {
       node = stack[top-1];
       if(node != NULL){
           top--; //将栈顶元素出栈
           if(node->right) stack[top++] = node->right;  //前序遍历中左右，所以要右左中进栈
           if(node -> left) stack[top++] = node -> left;
           stack[top++]= node;
           stack[top++]= NULL;
       }
       else {
           top--;//弹出空指针
           node = stack[top-1];
           top--; //弹出处理元素
           res[(*returnSize)++] = node ->val;
       }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 4、中序遍历

//统一风格的迭代法（我愿称之为空指针标记法）
int* inorderTraversal(struct TreeNode* root, int* returnSize){
   int* result =(int*)malloc(sizeof(int) * 101); //题目给出了树中节点数量的范围
    * returnSize =0;
    if(root == NULL){
        return result;
    }
    struct TreeNode* stack[101];
    struct TreeNode* node;
    int top = 0;
    stack[top++] = root;
    
    while(top>0)
    {
       node = stack[top-1];
       if(node != NULL){
           top--; //将栈顶元素出栈
           if(node->right) stack[top++] = node->right;  //中序遍历左中右，所以要以右中左的顺序进栈
           stack[top++]= node; 
           stack[top++] =NULL;
           if(node -> left) stack[top++] = node -> left;
       }
       else {
           top--;//将NULL弹出
           node = stack[top - 1]; //保存要处理元素
           top--; //将要处理元素弹出
           result[(*returnSize)++] = node ->val;  //将处理元素的值加入到结果数组
       }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 5、后序遍历

//统一迭代法
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* result = (int*)malloc(sizeof(int)* 101);
    * returnSize =0;
    if( root == NULL){
        return result;
    }
    struct TreeNode * node;
    struct TreeNode* stack[101];
    int top=0;
    stack[top++] =root;
    while(top > 0){
       node = stack[top-1];
       if(node != NULL){
           top--;//将栈顶元素弹出
           stack[top++] = node; //后序遍历左右中，所以要以中右左进
           stack[top++] = NULL;
           if(node -> right) stack[top++] = node->right;
           if(node -> left) stack[top++] = node -> left;
       }
       else{
           top--;//弹出NULL
           node = stack[--top];
           result[(*returnSize)++] = node->val;
       }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 五、二叉树的层序遍历

# 1、基础层序遍历

力扣题目链接 (opens new window)

# 1.1、题目

  • 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
  • img
示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]
示例 3：
c
输入：root = []
输出：[]
1
2
3
4
5
6
7
8
9
10
11
12
13

提示：

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

# 1.2、思路

  • 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

  • 需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

  • 而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

    使用队列实现二叉树广度优先遍历，动画如下：

    102二叉树的层序遍历

  • 简单来说就是： 1层1层进入队列，然后每进一层就将队列里当前层的元素出队，然后出队节点的左右子节点再入队，这样就完成了一层一层进队，并按层序输出

# 1.3、代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Return an array of arrays of size *returcnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int ** result = (int ** )malloc(sizeof(int* )*2000);  //结果数组（二维）
    int columnSizes[2000];  //记录每一行的列数
    * returnSize = 0; 
    if(root == NULL) return NULL;
    struct TreeNode* queue[2000];  //队列 
    int front=0,rear=0;  
    queue[rear++] = root;  //将root录入队列

    while(front != rear){
        int size = rear - front;
        //给结果数组每一层分配空间
        result[(*returnSize)] = (int*)malloc(sizeof(int)* size);  
        //记录没一层的列数
        columnSizes[(*returnSize)] = size;
        for(int i=0 ; i<size ; i++ ){
            //出队并赋值给二维数组
            struct TreeNode* node = queue[front++];
            result[(*returnSize)][i] = node ->val;
            //将处理节点的左右子节点加入队列
            if(node->left) queue[rear++] = node ->left;
            if(node->right) queue[rear++] = node -> right;
        }

        (*returnSize)++;
    }
    // 给returnSizes分配空间（不是定义，因为力扣里是已经定义过的了），并将之前记录的值赋给 returnSizes
    *returnColumnSizes =(int *)malloc(sizeof(int)* (*returnSize));
    for(int i=0;i< (*returnSize);i++){
        (*returnColumnSizes)[i] = columnSizes[i];
    }

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
  • 注意：result 每一层都需要分配size大小的空间

# 2、反向层序遍历

# 2.1 题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

img

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
    
示例 2：
输入：root = [1]
输出：[[1]]
    
示例 3：
输入：root = []
输出：[]
1
2
3
4
5
6
7
8
9
10
11

# 2.2 思路

  • 思路和基础层次遍历一样，就是最后把结果数组翻转

# 2.3 代码

int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int** result = (int**)malloc(sizeof(int *) * 2001); //创建二维结果数组
    * returnSize =0;
    if(root ==NULL) {
        return NULL;
    }
    int columnSizes[2001]; //记录每一层列数
    struct TreeNode* queue[2001]; //队列
    int front=0, rear=0;
    queue[rear++] = root;

    while( front != rear){
        int size = rear - front;

        result[(*returnSize)] = (int*)malloc(sizeof(int)* size);
         //记录每一层的列数
        columnSizes[(*returnSize)] = size;
        for(int i=0; i<size;i++){
            struct TreeNode* node = queue[front++];
            result[(*returnSize)][i] = node -> val;
            if(node->left) queue[rear++] = node->left;
            if(node->right) queue[rear++] = node->right;
        }
        columnSizes[(*returnSize)++] = size; //记录每一层的列数
    }

     //翻转二维数组
    for(int i =0; 2*i <(*returnSize);i++){
        int* temp = (int*) malloc(sizeof(int)*2001);
        temp = result[i];
        result[i] = result[(*returnSize)-1 -i];
        result[(*returnSize)-1 -i] = temp;
    }

    //将每层的列数录入 returnColumnSizes里
    * returnColumnSizes = (int * )malloc(sizeof(int)* (*returnSize));
    for(int i=0;i<(*returnSize); i++){
        (*returnColumnSizes)[i] = columnSizes[(*returnSize)-1-i];
    }

    return result;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
  • 注意: 这里因为数组翻转，所以我们在录入 returnColumnSizes 时也要记得反向录入

# 3、二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode） (opens new window)

# 3.1 题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

img

示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:
输入: [1,null,3]
输出: [1,3]

示例 3:
输入: []
输出: []
1
2
3
4
5
6
7
8
9
10
11

# 3.2 思路

  • 依旧层次遍历，但是每次只取最右边的元素进结果数组

# 3.3 代码

int* rightSideView(struct TreeNode* root, int* returnSize){
    int* result = (int *) malloc(sizeof(int)*100);
    * returnSize =0;
    if(root ==NULL){
        return result;
    }
    struct TreeNode * queue[100];
    int front =0,rear = 0;
    queue[rear++] = root;

    while(front != rear){

        int size =rear - front;
        for(int i =0 ; i<size; i++){
            struct TreeNode * node = queue[front++];
            if(i==size-1){
                result[(*returnSize)++] = node ->val;
            } 
            //因为上面的判断语句写的是 i = size-1，就是取层第一个进结果数组，所以下面要从左节点先进（层次遍历）
            //如果上面改成 i==0；那就要先进右结点
             if(node ->left) queue[rear++] = node -> left;
            if(node ->right) queue[rear++] = node -> right;
           
        }
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 4、二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode） (opens new window)

# 4.1、题目

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

img

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
1
2
3
4

提示：

  • 树中节点数量在 [1, 104] 范围内
  • -231 <= Node.val <= 231 - 1

# 4.2、思路

  • 思路和基础没变化，就是多了个sum来记录层总值，来进行计算
  • 注意：输出时是double型，所以不要习惯性写定义变量为 int

# 4.3、代码

double* averageOfLevels(struct TreeNode* root, int* returnSize){
    double* result = (double*)malloc(sizeof(int)* 10001);
    *returnSize =0;
    if(root == NULL){
        return NULL;
    }

    struct TreeNode* queue[10001];
    int front=0,rear=0;
    queue[rear++] =root;

    while(front != rear){
        int size = rear - front;
        double sum=0;
        for(int i=0;i<size;i++){
            struct TreeNode* node = queue[front++];
            sum += node->val;
            if(node->left) queue[rear++] = node->left;
            if(node->right) queue[rear++] = node->right;
        }
        result[(*returnSize)++] = sum/size;

    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 5、N叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode） (opens new window)

# 5.1 题目

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

img

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
1
2
3

img

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
1
2

提示：

  • 树的高度不会超过 1000
  • 树的节点总数在 [0, 10^4] 之间c

# 5.2 思路

  • 思路不变，主要是注意这里的结构体与之前不同

    •  * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
      1
      2
      3
      4
      5

  • 出现了一个很奇怪的bug，下面代码给(*returnColumnSizes) 分配空间的代码必须写到前面来，不然会报以下错误（但是基础层次遍历时并没有写到前面，而是搞了个数组来记录列数，再到最后再来正确的分配，而不是写前面直接分配了1000个int大小的空间？？？）

    • 
=================================================================
==20==ERROR: AddressSanitizer: attempting double-free on 0x621000003d00 in thread T0:
    #0 0x7fa2a558d40f in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:122
    #2 0x7fa2a4945082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x621000003d00 is located 0 bytes inside of 4000-byte region [0x621000003d00,0x621000004ca0)
freed by thread T0 here:
    #0 0x7fa2a558d40f in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:122
    #2 0x7fa2a4945082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
previously allocated by thread T0 here:
    #0 0x7fa2a558d808 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:144
    #3 0x7fa2a4945082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
SUMMARY: AddressSanitizer: double-free ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:122 in __interceptor_free
==20==ABORTING
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14

# 5.3 代码

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
    * returnSize=0;
    int ** result=(int**)malloc(sizeof(int *)*1000);
     //必须把这一句写到前面来，不然执行不错，但是提交就报错了
    (*returnColumnSizes) = (int*)malloc(sizeof(int)* 1000);
    if(root == NULL){
        return result;   
    }

    struct Node*queue[10000];
    int front=0,rear=0;
    queue[rear++]=root;
    while(front != rear){
        int size =rear-front;
        result[(*returnSize)] =(int*)malloc(sizeof(int)* size);
        for(int i=0;i<size;i++){
            struct Node* node = queue[front++];
            result[(*returnSize)][i] = node->val;
            for(int k=0;k < node->numChildren;k++){
                //因为 Node 节点里存的是一个指向 Node结构体指针的指针
                queue[rear++]= node->children[k];
            }
        }
       (*returnColumnSizes)[(*returcnSize)++] = size;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 6、找到树中每行的最大值

# 6.1、题目

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

img

示例1:
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：
输入: root = [1,2,3]
输出: [1,3]
1
2
3
4
5
6
7

提示：

  • 二叉树的节点个数的范围是 [0,104]
  • -2^31 <= Node.val <= 2^31 - 1

# 6.2、思路

  • 层序遍历,找每行的最大值

# 6.3、代码

int* largestValues(struct TreeNode* root, int* returnSize){
    int* result= (int*)malloc(sizeof(int)* 10000);
    *returnSize=0;
    if(root==NULL){
        return result;
    }

    struct TreeNode* queue[10000];
    int front=0,rear=0;
    queue[rear++] =root;
 
    while(front!= rear){
        int size = rear - front;
        int max = queue[front]->val;
        for(int i=0;i<size;i++){
            struct TreeNode* node = queue[front++];
            if(max < node ->val){
                max = node ->val;
            }
            if(node->left) queue[rear++]= node-> left;
            if(node->right) queue[rear++]= node-> right;
        }
        result[(*returnSize)++] = max;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 7、填充每个节点的下一个右侧节点指针

# 7.1 题目

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode） (opens new window)

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode） (opens new window)

  • 上面这两道题做法基本一样,所以就选第二个来看吧

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
1
2
3
4
5
6

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

img

示例1:
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例2:
输入：root = []
输出：[]
1
2
3
4
5
6
7
8

提示:

  • 树中的节点数在范围 [0, 6000] 内
  • -100 <= Node.val <= 100

# 7.2 思路

  • 判断是否是该层最后一个结点,是就next 指向 NULL
  • 如果不是就指向队列的头元素

# 7.3 代码

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */
struct Node* connect(struct Node* root) {
     if(root ==NULL){
        return root;
    }
	struct Node *queue[6000];
    int front=0,rear =0;
    queue[rear++] = root;
   

    while(front != rear){
        int size = rear - front;
        for(int i=0;i<size;i++){
            struct Node* node = queue[front++];
            //每层最后一个节点的next指向 NULL
            if(i==size-1){
                node->next =NULL ;
            }
             //每层非最后一个节点的next指向同层右侧的节点
            else{
                node -> next = queue[front];
            }
            if(node->left) queue[rear++] = node ->left;
            if(node->right) cqueue[rear++] = node ->right;
        }
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 8、二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode） (opens new window)

代码随想录 (programmercarl.com) (opens new window)

  • 有一些细节，看随想录了解

# 8.1 题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

  3
   / \
  9  20
    /  \
   15   7
1
2
3
4
5

返回它的最大深度 3 。

# 8.2 思路

  • 这道题没有告诉我们树的节点的数量范围,但是c语言的话,没办法定义一个不确定大小的数组来充当队列使用,所以这里用了递归的写法
    • 递归判断每个节点的左右节点,获取较大值

# 8.3 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

//递归，随想录写法
int maxDepth(struct TreeNode* root){
    //结束条件
    if(root == NULL) return 0;
    //递归处理
    int depth=0;
    int l_depth = maxDepth(root->left);   //左
    int r_depth = maxDepth(root->right);  //右
    depth = l_depth > r_depth ? l_depth :r_depth; //中
    return depth+1;
}

//递归
int maxDepth(struct TreeNode* root){
    if(root == NULL){
        return 0;
    }
    else {
        int hight_left = maxDepth(root -> left);
        int hight_right = maxDepth(root -> right);
        //使用fmax用于比较两数大小，返回较大值
        return fmax(hight_left,hight_right)+1;
    }
}

// 递归简单写法
int maxDepth(struct TreeNode* root){
    if(root == NULL) return 0;
    return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 9、二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode） (opens new window)

代码随想录 (programmercarl.com) (opens new window)

# 9.1 题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例1:

img

输入：root = [3,9,20,null,null,15,7]
输出：2
1
2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
1
2

# 9.2 层序思路

  • 层序入队,判断每个节点是否有左右子节点,都没有则结束入队,获取最小层数

# 9.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;
    }

    struct TreeNode* queue[100000];
    int front=0,rear=0;
    queue[rear++] =root;
    struct TreeNode* node=root; 
    int min_depth=0;
    
    //特殊情况，当root的没有左右子节点时，直接给返回 1
    if(node->left ==NULL&& node ->right == NULL){
        return 1;
    }
     
    //一层一层判断，遇到没有子节点的节点就跳出循环
    while(front != rear){
        int size = rear -front;
        if(node->left ==NULL && node->right ==NULL) break;
        min_depth++;
        for(int i =0;i<size;i++){
            node= queue[front++];
            if(node->left ==NULL && node->right ==NULL) break;
            if(node->left) queue[rear++] = node->left;
            if(node->right) queue[rear++] = node->right;
        }
    } 
    return min_depth;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 9.4 递归思路

  • 递归找到符合递归结束条件的结点,给予层数值
  • 回退时左右结点进行判断,找到层数小的结点返回
  • 注意: 我们比较的是子节点,但返回的是当前节点的层数值,所以返回的层数值要加1

# 9.5 递归代码

/**
 * 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 && root -> right == NULL){
        return 1;
    }
    
    int min_depth = INT_MAX;
    if(root->left) {
        min_depth= fmin(minDepth(root->left),min_depth);
    } 

    if(root->right) {
        min_depth= fmin(minDepth(root->right),min_depth);
    } 

    //判断的是子节点的层级所以要加1
    return min_depth +1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//随想录写法
int minDepth(struct TreeNode* root){
    if(root == NULL) {
        return 0;
    }
    int depth=0;
    int leftdepth = minDepth(root -> left);      //左
    int rightdepth = minDepth(root -> right);    //右
   
                                                 //中
    //当一个左子树为空，右不为空，这时不是最低点
    if(root->left == NULL && root ->right != NULL){
        depth = 1 + rightdepth;
    }
    //当一个右子树为空，左不为空，这时不是最低点
    else if(root->left != NULL && root ->right == NULL){
        depth = 1 + leftdepth;
    }
    else {
        depth = 1+ fmin(rightdepth,leftdepth);
    }
    return depth;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
编辑 (opens new window)
上次更新: 2023/09/13, 12:29:52
栈与队列
二叉树(中)

← 二叉树(中)→

最近更新
01
51单片机及补充知识
09-13
02
独立按键
09-13
03
LCD1602液晶显示器
09-13
更多文章>
Theme by Vdoing | Copyright © 2019-2023 Evan Xu | MIT License