二叉树层序遍历

解题思路

1. 准备一个队列开始bfs，但题目还要求把相同层的节点放在一起，所以我们可以用另一种bfs在树上，收集节点

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * 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().
 */
#define ERROR NULL 

typedef struct TreeNode* ELEMENT;

typedef struct queue {
	ELEMENT *data;//´æ·ÅÔªËØ 
	int head;//Ö¸Ïò¶ÓÍ·£¬Ò²¾ÍÊǶÓÁеĵÚÒ»¸öÔªËØ
	int tail;//Ö¸ÏòÏÂÒ»¸öÈë¶ÓµÄλÖã¬ËùÒÔÇø¼äΪ[head, tail) 
	int size;//¼Ç¼¶ÓÁÐÔªËصĸöÊý 
	int MaxSize;//¼Ç¼¶ÓÁÐ×î´óÄÜͬʱ´æÔÚµÄÔªËظöÊý 
}QNode, *Queue;

Queue createQueue(int n);//´´½¨Ò»¸ö´óСΪnµÄ¶ÓÁÐ 
bool isQueueFull(Queue q);//Åж϶ÓÁÐÊDz»ÊÇÂúÁË 
bool addQ(Queue q, ELEMENT item);//°ÑÔªËØitem´Ó¶ÓÁÐβ²¿¼ÓÈë 
bool isQueueEmpty(Queue q);//Åж϶ÓÁÐÊDz»ÊÇ¿Õ 
ELEMENT deleteQ(Queue q);//°Ñ¶ÓÁÐÍ·µÄÔªËسö¶Ó 
ELEMENT head(Queue q);//È¡³ö¶ÓÍ·µÄÔªËص«²»³ö¶Ó 
ELEMENT tail(Queue q);//È¡³ö¶ÓβµÄÔªËØ 
int queueSize(Queue q);//·µ»Ø¶ÓÁеÄÔªËظöÊý 
void FreeQueue(Queue q);//ÊͷŶÓÁÐ

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }

    Queue q = createQueue(2000);//最多不会超过2000个节点
    int** ans = (int**)malloc(sizeof(int*) * 2000);//那么最多也不超过2000层
    int* len = (int*)malloc(sizeof(int) * 2000);//记录每层的节点个数数组，最多不会超过2000层
    int i = 0;//记录层数

    addQ(q, root);//先把根节点放进队列

    while(!isQueueEmpty(q)) {//只要队列不为空层序遍历就没有结束
        int listSize = queueSize(q);//队列中元素的个数就是每层节点的个数
        ans[i] = (int*)malloc(sizeof(int) * listSize);//开辟数组存放节点的值
        len[i] = listSize;//每层节点的长度

        for (int j = 0; j < listSize; j++) {//把每层每个节点都处理了
            struct TreeNode* t = deleteQ(q);//弹出队列头的节点

            ans[i][j] = t -> val;//放入对应的层数中
            if (t -> left) {//如果有左孩子，就入队
                addQ(q, t -> left);
            }
            if (t -> right) {//如果有右孩子，就入队
                addQ(q, t -> right);
            }
        }
        i++;//层数加一
    }

    FreeQueue(q);//释放队列的空间
    *returnSize = i;//返回层数
    *returnColumnSizes = len;//返回每层的节点个数
    return ans;//返回收集的节点
}

Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//¿ª±ÙÒ»¸ö¶ÓÁÐ 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±Ù¿Õ¼äÀ´´æ·ÅÔªËØ 
	t -> head = 0;//³õʼ»¯¶ÓÍ· 
	t -> tail = 0;//³õʼ»¯¶Óβ 
	t -> MaxSize = n;//³õʼ»¯×î´óµÄ´óС
	t -> size = 0; 
	
	return t;//·µ»Ø¶ÓÁÐ 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//¶ÓÁÐÖÐûÓÐÔªËØ£¬ÄÇô¶ÓÁоÍÊÇ¿ÕµÄ 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//Èç¹û¶ÓÁÐÖÐÔªËظöÊýµÈÓÚ×î´óÄÜÈÝÄɵÄÔªËØ£¬ÄÇô¾ÍÂúÁË 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isQueueFull(q)) {//Èç¹û¶ÓÁÐÊÇÂúµÄ£¬²»ÄÜÈë¶Ó·µ»Øfalse 
		return false;
	}
	
	q -> data[q -> tail++] = item;//°ÑÔªËØitemÈë¶Ó£¬ÒòΪÊÇ[head, tail)£¬ËùÒÔ×ÔÔöÔÚºóÃæ 
	q -> tail %= q -> MaxSize;//Èç¹ûµ½ÁËÊý×é⣬»Øµ½Ï±ê0λÖà 
	q -> size++;//¶ÓÁÐÔªËظöÊý¼ÓÒ» 
	
	return true;//ÄÜÈë¶Ó·µ»Øtrue 
}
ELEMENT deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//Èç¹û¶ÓÁÐΪ¿Õ£¬ÄÇô¾Í²»Äܳö¶Ó£¬·µ»ØÒ»¸ö´íÎóÐÅÏ¢ 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//²»Îª¿Õ£¬·µ»Ø¶ÓÍ·£¬ÒòΪÊÇ[head, tail)µÄÇø¼ä£¬ËùÒÔ×ÔÔöÔÚºóÃæ 
}
ELEMENT head(Queue q)
{
	if (isQueueEmpty(q)) {//Èç¹û¶ÓÁÐΪ¿Õ£¬Ã»ÓжÓÍ·£¬ÊÇ·Ç·¨µÄ £¬·µ»ØÒ»¸ö´íÎóÐÅÏ¢ 
		return ERROR;
	}
	
	return q -> data[q -> head];//¶ÓÁв»Îª¿Õ£¬·µ»Ø¶ÓÁÐÍ·µÄÔªËØ£¬·µ»Ø¶ÓÍ·ÔªËز»ÓÃÌØÅУ¬ÒòΪÊÇ[head, tail)£¬ÄÇôhead±Ø¶¨ÊÇÓÐЧµÄϱ꣬ËùÒÔÖ±½Ó·µ»Ø 
}
ELEMENT tail(Queue q)
{
	if (isQueueEmpty(q)) {//Èç¹û¶ÓÁÐΪ¿Õ£¬Ã»ÓжÓ⣬ÊÇ·Ç·¨µÄ £¬·µ»ØÒ»¸ö´íÎóÐÅÏ¢ 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//Èç¹ûq -> tail - 1 < 0£¬´ú±íÊÇ´ÓMaxSize - 1ϱê¹ýÀ´µÄ
	//È»ºótial±ä³É0ÁË£¬ËùÒÔ¶ÓβԪËØʵ¼ÊÔÚMaxSize - 1λÖã¬ÆäËûλÖò»ÓÃÌØÅÐ 
	//ÒòΪÊÇ[head, tail)ËùÒÔ¶ÓβԪËØÔÚtail - 1λÖ㬵«ÒòΪÊÇ»·ÐÎÊý×飬¿ÉÄÜÊÇ´ÓMaxSizeϱê¹ýÀ´µÄ
	//ËùÒÔtail == 0ÊǼõÒ»£¬Êý×éÔ½½çÁË£¬Òò´ËÒªÌØÅÐ 
}
int queueSize(Queue q)
{
	return q -> size;//ÒòΪÊÇ[head, tail)µÄÇø¼äËùÒÔ£¬Ö±½ÓÏà¼õ¾ÍÊǶÓÁеÄÔªËظöÊý 
}
void FreeQueue(Queue q)
{
	free(q -> data);//ÏÈÊͷŵôÔªËصÄÄÚ´æ¿Õ¼ä 
	free(q);//ÔÙÊͷŵô¶ÓÁеÄÄÚ´æ¿Õ¼ä 
}

二叉树的最大宽度 

解题思路

1. 利用层序遍历就可以解决这个问题，每次访问一层的时候去求每一层的最大宽度，再更新答案就可以了。
2. 但还需要一个队列来记录每个节点再满二叉树中编号不然无法求宽度。

代码实现

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

typedef struct TreeNode* Tree;

int widthOfBinaryTree(struct TreeNode* root){
    unsigned long long iq[3001] = {0};//用来记录每个节点的编号
    Tree nq[3001] = {0};//用数组来模拟队列
    int l = 0;//队列的头
    int r = 0;//队列的尾
    unsigned long long ans = 1;//答案

    nq[r] = root;//把根节点放入队列
    iq[r++] = 1;//根节点的编号为1

    while(l < r) {//只要队列还有节点，是左闭右开[l, r)区间所以是l < r
        int size = r - l;//队列中的元素个数，也是每层的节点数

        for (int i = 0; i < size; i++) {//访问每一层节点
            Tree t = nq[l];//取出节点
            unsigned long long id = iq[l++];//取出对应的编号

            if (t -> left) {//有左孩子
                nq[r] = t -> left;//左孩子放入队列
                iq[r++] = id * 2;//把左孩子编号也放入队列
            }

            if (t -> right) {//有右孩子
                nq[r] = t -> right;//右孩子放入队列
                iq[r++] = id * 2 + 1;//把右孩子编号也放入队列
            }
        }

       unsigned long long max = 0;

       if (l < r) {//当前层还有节点，也就是当前层至少有一个非空节点
           max = iq[r - 1] - iq[l] + 1;//左闭右开所以最后一个节点的编号在r - 1位置，加1因为它本身也要算一个宽度，所以要加一
       }

        if (ans < max)//更新最大宽度
        {
            ans = max;
        }
    }

    return ans;
}

二叉树最大深度(二叉树的高度)

方法一(递归)

解题思路

1. 只要分别求出左子树和右子树的高度,然后再拿出其中高度最大的再加一就是二叉树的最大高度了。
2. 所以对于任意一个二叉树我们都可以转换成这样一个问题，那么这就变成了一个子问题了，那么我们就可以递归来求解了

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b) {//返回a和b中的最大值
    return a >= b? a: b;
}

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {//如果节点为NULL，返回0，因为没有节点高度为0
        return 0;
    }

    return max(1 + maxDepth(root -> left), 1 + maxDepth(root -> right));//返回左子树的深度和右子树的深度的最大值，因为当前节点还要算高度所以还要加1，所以我这个函数实际上返回的是整个二叉树的高度，直接两边子树的高度都加1，然后返回其中的最大值，也就是二叉树的最大高度了
}

方法二(bfs)

解题思路

1. 层序遍历二叉树，就可以得到二叉树的最大深度也就是二叉树的高度，因为层序遍历得到的层数就是二叉树的最大深度也就是二叉树的高度，这个是根据层序遍历的性质得到的。 

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root) {
    if (root == NULL)//如果没有节点那么高度为0
    {
        return 0;
    }

    struct TreeNode* q[10001];//用数组来模拟队列
    int l = 0;//队列头
    int r = 0;//队列尾
    int depth = 0;//深度

    q[r++] = root;//根节点入队

    while(l < r)//只要队列还有节点，区间是左闭右开[l, r)，所以当l == r时队列中没有节点
    {
        int size = r - l;//取出队列中元素个数，也就是当前层的节点个数
        depth++;//深度加一，因为深度等于层数

        for (int i = 0; i < size; i++) {//访问每层的节点
            struct TreeNode* t = q[l++];//弹出队列头
        
            if (t -> left)//有左孩子
            {
                q[r++] = t -> left;//左孩子入队
            }
            if (t -> right)//有右孩子
            {
                q[r++] = t -> right;//右孩子入队
            }
        }
    }

    return depth;//返回层数，也就二叉树的高度
}

二叉树的最小高度

方法一(dfs)

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

void pre(struct TreeNode* root, int depth, int * ans)//前序遍历
{
    if (!root) {//如果当前为空结束当前递归返回上一层
        return ;
    }

    if (!root -> left && !root -> right) //如果是叶子节点
    {
        if (depth < *ans) {//比较深度，如果比最小深度还要小，那么更新最小深度
            *ans = depth;//更新最小深度
        }
        return ;//结束当前递归
    }

    pre(root -> left, depth + 1, ans);//遍历左子树，深度加1,因为要算当前节点
    pre(root -> right, depth + 1, ans);//遍历右子树，深度加1，因为要算当前节点
}

int minDepth(struct TreeNode* root) {
    if (root == NULL) {//如果没有节点最小深度为0
        return 0;
    }

    int ans = 1 << 30;//初始化为一个极大值
    pre(root, 1, &ans);//前序遍历
    return ans;//返回结果
}

方法二(层序遍历)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int minDepth(struct TreeNode* root) {
    if (root == NULL)//如果没有节点那么最小深度就是0
    {
        return 0;
    }

    struct TreeNode* q[100001];//数组模拟队列
    int l = 0;//队列头
    int r = 0;//队列尾
    int depth = 0;//深度也就是层数
    int flag = 0;//标志要不要跳出循环

    q[r++] = root;//根节点入队
    
    while(l < r)//只要队列里面还有节点
    {
        int size = r - l;//当前层的节点个数
        depth++;//层数加一或者深度加一

        for (int i = 0; i < size; i++)//访问当前层的每一个节点
        {
            struct TreeNode* t = q[l++];//队列头出队

            if (!t -> left && !t -> right)//如果当前节点已经是叶子节点
            {
                flag = 1;//标志需要退出整个循环
                break;//跳出当前循环
            }

            if (t -> left) {//有左孩子
                q[r++] = t -> left;//左孩子入队
            }

            if (t -> right) {//有右孩子
                q[r++] = t -> right;//右孩子入队
            }
        }

        if (flag == 1) {//如果要跳出整个循环，就跳出，不然就继续bfs
                break;
        }
    }

    return depth;//最后的答案就是最小深度，因为碰到叶子节点就跳出了
}

二叉树的完全性检验

力扣题目链接

方法一(借助另一个编号队列)(超级好懂)

解题思路

1. 根据完全二叉树的定义我们可以知道如果给每个节点编个号，那么它的编号必定连续。反之如果它不是完全二叉树那么它的编号必定不连续。
2. 因此我们只要我们次判断前一个节点的编号和当前节点的编号是否连续就可以了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isCompleteTree(struct TreeNode* root) {
    struct TreeNode* nq[101];//节点队列
    unsigned long long iq[101];//编号队列
    int l = 0;//队列头
    int r = 0;//队列尾
    unsigned long long pre = 0;//前一个节点的编号,默认根节点的前一个编号是0
    bool flag = false;//标志要不要退出循环
    bool ans = true;//答案

    nq[r] = root;//根节点入队
    iq[r++] = 1;//根节点的编号入编号队列

    while(l < r)//只要队列里面还有节点，是左闭右开区间[l, r),所以l == r表示队列为空
    {
        int size = r - l;//取出队列里面的元素个数

        for (int i = 0; i < size; i++)//访问队列里面的每个元素
        {
            struct TreeNode* t = nq[l];//队列头节点出队
            unsigned long long id = iq[l++];//把节点对应的编号出队队列
    
            if (pre + 1 != id) {//如果编号不是连续的表示不是一颗完全二叉树
                flag = true;//设置为true表示等下要跳出外层循环
                ans = false;//不是完全二叉树就是false
                break;
            }

            if (t -> left) {//有左孩子
                nq[r] = t -> left;//左孩子入队
                iq[r++] = 2 * id;//左孩子对应的编号入队
            }

            if (t -> right)//有右孩子
            {
                nq[r] = t -> right;//右孩子入队
                iq[r++] = 2 * id + 1;//右孩子对应的编号入队
            }
            pre = id;//更新前一个节点的编号
        }

        if (flag) {//如果为真表示要跳出循环
            break;
        }
    }

    return ans;
}

方法二(完全二叉树的定义)

解题思路

1. 第一种情况:根据定义如果一个节点有右孩子没有左孩子那么这颗树必定不是一颗完全二叉树
2. 第二种情况:如果一个节点有孩子不全的情况，那么后面的所有节点是叶子节点，它就是一个完全二叉树，否则它不是一个完全二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isCompleteTree(struct TreeNode* root) {
    struct TreeNode* nq[101];//节点队列
    int l = 0;//队列头
    int r = 0;//队列尾
    bool leaf = false;//表示有没有遇到孩子不全的情况

    nq[r++] = root;//根节点入队

    while(l < r)//表示队列里面还有节点
    {
        struct TreeNode* t = nq[l++];//队列头出队

        if ((!t -> left && t -> right)//有右孩子但没有左孩子，那么不是完全二叉树返回false
         || (leaf && (t -> left || t -> right))) {//有遇到孩子不全的情况并且不是叶节点，那么不是完全二叉树
            return false;
        }

        if (t -> left) //有左孩子
        {
            nq[r++] = t -> left;//左孩子入队
        }

        if ( t -> right ) {//有右孩子
            nq[r++] = t -> right;//右孩子入队
        }

        if (!t -> left || !t -> right) {//遇到孩子不全的情况
            leaf = true;
        }
    }

    return true;
}

二叉树的最近公共祖先

力扣题目链接

解题思路

1. 第一种情况，q和p不是包含关系，p不是q的祖先或者q不是p的祖先。
2. 第二种情况，p和q是包含关系，p是q的祖先，或者q是p的祖先
3. 返回当前节点的情况:当前节点是空节点或者碰到p或者q了
4. 左右子树都找到了，返回当前节点
5. 只有左子树找到了返回左子树的结果
6. 只有右子树找到了返回右子树的结果
7. 左右子树都没有找到:返回空节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == q || root == p) {//遇到了就返回遇到的节点，没有遇到返回空
        return root;
    }

    struct TreeNode* lAns = lowestCommonAncestor(root -> left, p, q);//左子树去搜索p和q
    struct TreeNode* rAns = lowestCommonAncestor(root -> right, p, q);//右子树去搜索p和q

    if (!lAns && !rAns) {//左右子树都没有找到p或者q返回空
        return NULL;
    }

    if (lAns && rAns) {//如果左右子树都找到了，代表这个节点就是最近的公共祖先
        return root;
    }

    //只剩下一种情况了，要么左子树找到了，要么右子树要找到了
    return lAns != NULL? lAns: rAns;//返回不是空的那个，因为一个为空，另一个就不为空
}

本栏目推荐文章
• 记一次docker出全linux的内网渗透题目(仿照2023铸剑杯)
• 盘点一个AI都无法解决的Python基础题目（下篇）
• 低压电工题目解析
• 2024年题目选讲
• 二叉树面试高频题目
• 题目整理（寒假）
• 一、软考中级软件设计师（知识产权部分）知识点+对应题目
• 2024年1月2日题目总结
• 算法题遇到不会的题目应该怎么学习？
• div4 题目

题目子题目 题目pta 题目oop codeforces题目 题目1017 20230712题目 题目java 题目acm 题目2024 题目cka