二叉树相关题目

文章目录

前言思维图建议递归的3要素二叉树的创建

OJ题目思路代码 二叉树的销毁

思路代码 二叉树的深度

思路代码 二叉树节点个数

思路代码 二叉树叶子节点个数

思路代码 二叉树第k层节点个数

思路代码 二叉树查找值为x的第一个节点

思路代码 判断二叉树是否是完全二叉树

思路：队列代码 判断2个二叉树是否相等

思路代码

前言

本文介绍二叉树的功能实现

博主收录的问题:New Young

转载请标明出处：New Young

思维图

建议

二叉树是一种递归结构!!!!!!!!!,这一点一定要时刻牢记。递归利用 分而治之的思想 ，对于解决二叉树问题，很方便递归我们一般建议先判断假的情况，这会很大层度方便解决问题。在使用递归时，如果不能一下完成所有代码，可以先完成大致的部分，之后慢慢补齐细节问题。

递归的3要素

递归函数返回值的使用问题递归函数的参数设置问题递归的结束条件的判断问题。

二叉树的创建 OJ题目

oj链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

思路

树是一个递归结构，因此这里使用递归的思路构建二叉树。

函数返回值问题。构建完成的二叉树，必然需要根结点的地址。

函数形参问题：

 root->left = BinaryTreeCreat(++str);
 root->right= BinaryTreeCreat(++str);

如果这里使用++str，当递推到本层后，对于右子树的构建，访问字符串可能就会是已访问的位置。因此这里可以使用 全局变量，或者一个指针i，通过改变i的指向内存中的数据，我们就可以正确控制访问字符串。

代码

#include 
#include  
#include 
#include 
//思路，二叉树是递归结构，为了构建二叉树，所以应该先构建好二叉树的左右子树，
//BTNode* BinaryTreeCreat(const char*str,int *i);//创建二叉树.

//但是对于字符串来说，单一的通过++str，是不行的---当回归时会发生意外的情况。
//因此这里使用 指针变量i来控制访问字符串。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;

}BTNode;
void InOrder(BTNode* root)// 二叉树中序遍历
{
	if (root==NULL)
	{
        
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
BTNode* BuyNode(BTDataType x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp==NULL)
	{
		printf("tmp==NULLn");
		exit(-1);
	}
	tmp->data = x;
	tmp->left = NULL;
	tmp->right = NULL; 

	return tmp;
}
BTNode* BinaryTreeCreat(const char*str,int *i)//创建二叉树.
{    
	if (str[*i] == ''|| str[*i]== '#')
	{
		++(*i);
		return NULL;
	}
    
 	BTNode* root = BuyNode(str[*i]);
	++(*i);
	root->left = BinaryTreeCreat(str,i);
	root->right= BinaryTreeCreat(str,i);
	return root;
}

int main()
{
    
    char arr[100]={0};
    while(fgets(arr,100,stdin))
    {
        int i=0;
          BTNode*root= BinaryTreeCreat(arr,&i);
        InOrder(root);   
    }
}

二叉树的销毁 思路

要想销毁根结点，必然先销毁左右子树—递归分而治之。

代码

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

二叉树的深度 思路

代码

int BinaryTreeH(BTNode* root)//二叉树的深度
{
	return root ? 0:1+fmax(BinaryTreeH(root->left),BinaryTreeH(root->right));
}

二叉树节点个数 思路

因为二叉树也是由很多小二叉树构成，因此计算一个二叉树的结点个数，先 求小二叉树的节点个数，这就成了一个递归问题，分而治之。递归结束条件是遇到空小二叉树。

代码

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

二叉树叶子节点个数 思路

当结点的left=right==NULL,才是叶节点

同样也需要求左右子树—分而治之—递归实现。

代码

int BinaryTreeLeafSize(BTNode* root)// 二叉树叶子节点个数
{
	if (root == NULL)//空树是没有叶结点
	{
	
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

二叉树第k层节点个数 思路

这里认为第一层的下标是从1开始的。因为递归是从二叉树的第一层开始的，而要想去到二叉树的第k层，需要一些判断，二叉树是由小二叉树构成的，去求第k层，也就是去看第k层有多少个二叉树根结点。通过–k，当k=1时，代表递归到达第k层

代码

int BinaryTreeLevelKSize(BTNode* root, int k)// 二叉树第k层节点个数// 二叉树第k层节点个数
{
	assert(k >=1);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	
	}
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}

二叉树查找值为x的第一个节点 思路

同样使用分而治之的思路因为不确定x是否唯一，因此我们可以先遍历左子树，之后右子树。
同时通过一个变量去记录结点地址，防止没必要的重复递归.—这一步在很多递归题目中都有体现，记录结果可以防止没必要的函数栈帧的时间开销。判断是否找到的条件是：
我们可以发现，如果一直递归，必然要遇到空树.
如果在遇到空树前找到了，递归就结束了。
如果遇到空树，说明该路没找到.返回NULL

代码

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)// 二叉树查找值为x的第一个节点
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftroot = BinaryTreeFind(root->left, x);
	if (leftroot != NULL)
	{
		return leftroot;
	}
	
	BTNode* rightroot = BinaryTreeFind(root->right, x);
	if (rightroot != NULL)
	{
		return rightroot;
	}
	return NULL;
}

判断二叉树是否是完全二叉树 思路：队列

如果以层序遍历一个二叉树，如果当队列头为NULL,之后都是NULL，那么为完全二叉树，反之为非完全二叉树。原因：

完全二叉树不可能在一层为满的情况下，在下一层有结点。

虽然我们可以通过去右子树存在，左子树不存在在一定层度判断是否为完全二叉树，但是这不严谨。如下图，虽然满足条件，但却不是完全二叉树。

代码

bool BinaryTreeComplete(BTNode* root)// 判断二叉树是否是完全二叉树
{		 
	 Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueTop(&q);
		QueuePop(&q);
		if (front == NULL)
		{
				break;
		}
		else
		{
				QueuePush(&q, front->left);
				QueuePush(&q, front->right);
		}
	}
	
	// 遇到空了以后，检查队列中剩下的节点
	// 1、剩下全是空给，则是完全二叉树
	// 2、剩下存在非空，则不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueTop(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}	
QueueDestroy(&q);
return true;	
	
}

判断2个二叉树是否相等 思路

判断2个二叉树是否相等，必然要去判断左右子树是否相等。

因此递归–分而自治

代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//最小的树的左右孩子都为空，代表为真.
if(p==NULL&&q==NULL)
{
    return true;
}
//p.q其中一个为空代表fasle.
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);
}