1. Toy模板网首页
  2. > Toy博客

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

9月前 作者：认真学习的小雅兰. 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

各位CSDN的uu们你们好呀，今天小雅兰的内容仍然是二叉树和Leetcode每日一题，下面，就让我们进入二叉树的世界吧！！！

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

这个题目需要重新定义一个函数，函数参数需要有左子树和右子树，题目所给定的函数无法解决问题。

bool _isSymmetric(struct TreeNode* leftRoot,struct TreeNode* rightRoot)
{
    //左子树和右子树同时为空
    if(leftRoot==NULL&&rightRoot==NULL)
    {
        return true;
    }
    //一棵树为空，另一棵树不为空
    if((leftRoot==NULL&&rightRoot!=NULL)||
    (leftRoot!=NULL&&rightRoot==NULL))
    {
        return false;
    }
    //左子树的根和右子树的根不相等
    //这就必然不对称
    if(leftRoot->val!=rightRoot->val)
    {
        return false;
    }
    return _isSymmetric(leftRoot->left,rightRoot->right)&&
            _isSymmetric(leftRoot->right,rightRoot->left);
}
bool isSymmetric(struct TreeNode* root){
    return _isSymmetric(root->left,root->right);
}

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

每个不为空的结点，都可以认为是一棵子树的根 

//两棵树相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //两个都为空
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    //一个为空，另一个不为空
    if((p==NULL&&q!=NULL)||(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;
    }
    //root和subRoot相同
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    //root的左子树与subRoot有相同或者root的右子树与subRoot有相同
    //满足其中一个条件即可，所以用||
    return isSubtree(root->left,subRoot)||
            isSubtree(root->right,subRoot);
}

 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

递归里面传数组下标要注意！！！

每个栈帧里面都有一个数组下标！！！ 

所以要传数组下标的地址。

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
//递归里面传数组下标要注意！！！
//每个栈帧里面都有一个i
void preorder(struct TreeNode* root,int* a,int* pi)
{
    if(root==NULL)
    {
        return;
    }
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //root是输入型参数，returnSize是返回型参数
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(*returnSize*sizeof(int));
    int i=0;
    preorder(root,a,&i);
    return a;
}

 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

当然，这个题目还有另外一种解法，就是把i作为全局变量，但是这样要特别注意，稍有不慎就会出错

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

int TreeSize(struct TreeNode* root)

{

    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;

}

//递归里面传数组下标要注意！！！

//每个栈帧里面都有一个i

int i=0;

void preorder(struct TreeNode* root,int* a)

{

    if(root==NULL)

    {

        return;

    }

    a[i++]=root->val;

    preorder(root->left,a);

    preorder(root->right,a);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize){

    //root是输入型参数，returnSize是返回型参数

    *returnSize=TreeSize(root);

    int* a=(int*)malloc(*returnSize*sizeof(int));

    i=0;

    preorder(root,a);

    return a;

}

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

int TreeSize(struct TreeNode* root)

{

    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;

}

void inorder(struct TreeNode* root,int* a,int* pi)

{

    if(root==NULL)

    {

        return;

    }

    inorder(root->left,a,pi);

    a[(*pi)++]=root->val;

    inorder(root->right,a,pi);

}

int* inorderTraversal(struct TreeNode* root, int* returnSize){

    //root是输入型参数，returnSize是返回型参数

    *returnSize=TreeSize(root);

    int* a=(int*)malloc(*returnSize*sizeof(int));

    int i=0;

    inorder(root,a,&i);

    return a;

}

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

int TreeSize(struct TreeNode* root)

{

    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;

}

void postorder(struct TreeNode* root,int* a,int* pi)

{

    if(root==NULL)

    {

        return;

    }

    postorder(root->left,a,pi);

    postorder(root->right,a,pi);

     a[(*pi)++]=root->val;

}

int* postorderTraversal(struct TreeNode* root, int* returnSize){

    //root是输入型参数，returnSize是返回型参数

    *returnSize=TreeSize(root);

    int* a=(int*)malloc(*returnSize*sizeof(int));

    int i=0;

    postorder(root,a,&i);

    return a;

}

 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

1出来带2和4，2出来带3和NULL，4出来带和6 

写这个代码的核心是得有一个队列！！！

Queue.h的内容：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
// 队列的结构 
typedef struct Queue
{
	QueueNode* phead;//头指针
	QueueNode* ptail;//尾指针
	int size;
}Queue;
// 初始化队列
void QueueInit(Queue* pq);

// 销毁队列 
void QueueDestroy(Queue* pq);

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x);

// 队头出队列 
void QueuePop(Queue* pq);

// 获取队列头部元素 
QDataType QueueFront(Queue* pq);

// 获取队列队尾元素 
QDataType QueueBack(Queue* pq);

// 获取队列中有效元素个数 
int QueueSize(Queue* pq);

// 检测队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c的内容：

#include"Queue.h"
// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->phead;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	//是空队列的情况
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
// 检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}
// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//1.一个结点
	//2.多个结点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//相当于头删
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

层序遍历源代码：

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root != NULL)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树销毁

//二叉树销毁
void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

通 过 前 序 遍 历 的 数 组 " A B D # # E # H # # C F # # G # # " 构 建 二 叉 树

根        左子树        右子树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

#include <stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatTree(char* a,int* pi)
{
    if(a[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root=BuyNode(a[*pi]);
    (*pi)++;
    root->left=CreatTree(a,pi);
    root->right=CreatTree(a,pi);
    return root;
}
//中序
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
int main()
{
    char a[100];
    scanf("%s",a);
    int i=0;
    BTNode*root=CreatTree(a,&i);
    InOrder(root);
    printf("\n");
    return 0;

}

 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

 二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

判断二叉树是否是完全二叉树

完全二叉树的特征是：层序遍历去走，它是连续的！！！

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

1出来带2和4，2出来带3和NULL，4出来带5和6，3出来带NULL和NULL，但是，3后面的NULL的后面竟然还有非空，这就证明此树是一棵非完全二叉树。

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

1出来带2和4，2出来带3和7，4出来带5和6，3出来带8和NULL，7出来带NULL和NULL，5出来带NULL和NULL，6出来带NULL和NULL，8出来带NULL和NULL，也就是说，队列里面的全都是空了，这一定是一棵完全二叉树。

//判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root != NULL)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//遇到空就跳出循环
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//检查后面的结点有没有非空
	//有非空，就不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ A ）

A ABDHECFG

B ABCDEFGH

C HDBEAFCG

D HDEBFGCA

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（ A ）

A E

B F

C G

D H

此题与中序遍历无关（中序遍历是迷惑人的），光看先序遍历就可以看出来，先序遍历就是根        左子树        右子树，所以E就是根结点。

但如果是想还原出这棵二叉树，中序遍历就很重要啦！！！

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

3.设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为（ D ）。

A adbce

B decab

C debac

D abcde

后序遍历序列最后一个是a,所以a就是根节点！！！

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为（ A ）

A FEDCBA

B CBAFED

C DEFCBA

D ABCDEF

二叉树的性质

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树

整个二叉树的源代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Queue.h"
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}

BTNode* CreatBinaryTree()
{
    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;
    return node1;
}

//前序
void PrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

//中序
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

//后序
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}
 

二叉树结点个数
//int size = 0;//全局变量
//int BTreeSize(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    else
//    {
//        ++size;
//    }
//    BTreeSize(root->left);
//    BTreeSize(root->right);
//}
二叉树结点个数
//int BTreeSize(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    else
//    {
//        return BTreeSize(root->left) + BTreeSize(root->right) + 1;
//    }
//}


//二叉树结点个数
int BTreeSize(BTNode* root)
{
    return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}


//求叶子结点的个数
int BTreeleafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return BTreeleafSize(root->left) + BTreeleafSize(root->right);
}

//求二叉树的高度
int BTreeHeight(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        int leftHeight = BTreeHeight(root->left);
        int rightHeight = BTreeHeight(root->right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
}


// 二叉树第k层节点个数
int BTreeLevelKSize(BTNode* root, int k)
{
    assert(k > 0);
    if (root == NULL)//无论k是多少
    {
        return 0;
    }
    //root一定不为空
    if (k == 1)
    {
        return 1;
    }
    //root不为空并且k不为1
    return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}


// 二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x)
    {
        return root;
    }
    BTNode* ret1 = BTreeFind(root->left, x);
    if (ret1)
    {
        return ret1;
    }
    BTNode* ret2 = BTreeFind(root->right, x);
    if (ret2)
    {
        return ret2;
    }
    return NULL;
}


//层序遍历
void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root != NULL)
    {
        QueuePush(&q, root);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%d ", front->data);
        if (front->left != NULL)
        {
            QueuePush(&q, front->left);
        }
        if (front->right != NULL)
        {
            QueuePush(&q, front->right);
        }
    }
    printf("\n");
    QueueDestroy(&q);
}


//二叉树销毁
void BTreeDestroy(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BTreeDestroy(root->left);
    BTreeDestroy(root->right);
    free(root);
}


//判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root != NULL)
    {
        QueuePush(&q, root);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        //遇到空就跳出循环
        if (front == NULL)
        {
            break;
        }
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    //检查后面的结点有没有非空
    //有非空，就不是完全二叉树
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front != NULL)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

int main()
{
    BTNode* root = CreatBinaryTree();
    PrevOrder(root);
    printf("\n");

    InOrder(root);
    printf("\n");

    PostOrder(root);
    printf("\n");

    /*BTreeSize(root);
    printf("BTreeSize:%d\n", size);

    size = 0;
    BTreeSize(root);
    printf("BTreeSize:%d\n", size);

    size = 0;
    BTreeSize(root);
    printf("BTreeSize:%d\n", size);*/

    printf("BTreeSize:%d\n",BTreeSize(root));

    printf("BTreeleafSize:%d\n", BTreeleafSize(root));

    printf("BTreeHeight:%d\n", BTreeHeight(root));

    printf("BTreeLevelKSize:%d\n", BTreeLevelKSize(root, 3));

    printf("BTreeFind:%p\n", BTreeFind(root, 3));

    LevelOrder(root);

    BTreeDestroy(root);
    root = NULL;

    return 0;
}
 

好啦，小雅兰的今日分享就到这里啦，还要继续加油学习噢！！！

二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”,leetcode每日一题,数据结构与算法,leetcode,算法,职场和发展,数据结构,b树文章来源地址https://www.toymoban.com/news/detail-576841.html

到了这里，关于二叉树（下）+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode - 每日一题】823. 带因子的二叉树 （2023.08.29）

    元素都大于1，元素不重复。 计数满足要求的二叉树（每个非叶结点的值应等于它的两个子结点的值的乘积）的数量。 元素可以重复使用。 自上而下动态规划。 所有元素大于1，所以不会有 自己×自己=自己 的情况； 元素本身就是一棵二叉树，所以将 dp 初始化为全 1； 将数组

    2024年02月10日
    浏览(38)
  • (树) 剑指 Offer 27. 二叉树的镜像 ——【Leetcode每日一题】

    (树) 剑指 Offer 27. 二叉树的镜像 ——【Leetcode每日一题】

    难度：简单 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 镜像输出： 示例 1： 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1] 限制 ： 0 = 节点个数 = 1000 注意 ：本题与 226. 翻转二叉树 相同。 💡思路：递归 我们从根节点开始，递归地对树进行遍历: 如果

    2024年02月13日
    浏览(34)
  • 【算法与数据结构】226、LeetCode翻转二叉树

    【算法与数据结构】226、LeetCode翻转二叉树

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：这道题的思路很简单，本质上就是遍历每一个节点，然后交换左右节点。我们可以用前中后遍历或者是层次遍历法来做，参考这两篇文章，【算法与数据结构】144、94、145LeetCode二

    2024年02月16日
    浏览(41)
  • 【算法与数据结构】654、LeetCode最大二叉树

    【算法与数据结构】654、LeetCode最大二叉树

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似，相关代码可以互相参考，本题明示了要用递归来做，那么递归三要素不可缺少： 输入参数和返

    2024年02月09日
    浏览(45)
  • 【LeetCode】【数据结构】二叉树必刷OJ题

    【LeetCode】【数据结构】二叉树必刷OJ题

    👀 樊梓慕： 个人主页   🎥 个人专栏： 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子，都是对生命的辜负 目录 前言 【LeetCode】226.翻转二叉树 【LeetCode】100.相同的树 【LeetCode】5.对称二叉树 【LeetCode】9.另一颗树的子树

    2024年02月08日
    浏览(51)
  • 每日一题：LeetCode-589.N叉树的前序遍历序列构造二叉树

    每日一题：LeetCode-589.N叉树的前序遍历序列构造二叉树

    前言： 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉 算法 👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月05日
    浏览(40)
  • 每日一题：leetcode 1448 统计二叉树中好节点的数目

    每日一题：leetcode 1448 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树，请你返回二叉树中好节点的数目。 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。 示例 1： 示例 2： 示例 3： 提示： 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 思路

    2024年02月11日
    浏览(40)
  • Leetcode每日一题：1448. 统计二叉树中好节点的数目

    Leetcode每日一题：1448. 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树，请你返回二叉树中好节点的数目。 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。 示例 1： 示例 2： 示例 3： 提示： 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 显然

    2024年02月11日
    浏览(37)

  • 数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)

    二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 描述 就 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。 示例 1 示例 2 提示 树中节点数的范围在 [0, 1 0 5 10^5 1 0 5 ] 内

    2024年02月06日
    浏览(44)
  • 2023-08-25 LeetCode每日一题（统计二叉树中好节点的数目）

    2023-08-25 LeetCode每日一题（统计二叉树中好节点的数目）

    点击跳转到题目位置 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。 示例 1： 示例 2： 示例 3： 提示： 二叉树中节点数目范围是 [1, 10 5 ] 。 每个节点权值的范围是 [-10

    2024年02月11日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包