二叉树OJ题目

一.二叉树第k层结点个数

有这样的一个思路：我既然要求第k层的结点个数，我肯定是要用到递归，那么当我在递归到第k层的时候我就开始判断，这一层是不是我所需要的那一层，如果是，就计数有几个节点，如果不是，就继续递归。就像这个图：

我们在往下递归的时候，我们的k也随之递减，当k为1的时候，这里就是我们要求的那一层。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) 
		   + BinaryTreeLevelKSize(root->right, k - 1);
}

二.二叉树查找值为x的结点

这个要处理的细节就比较多了

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data = x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)//如果ret1不为NULL就说明找到了
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)//与ret1同理
		return ret2;

	return NULL;//最底层的叶子结点找完了，依然没有符合的，返回NULL
}

在这个函数中依旧是需要不断的递归，首先是一直往左子树走，如果没有找到，就要一直到左子树为空树，然后再去右子树找，层层递进。要注意的是当我们在往左子树和右子树递归的时候，我们一定要把值给记录下来再去返回。

如图所示，我们要去找6的话：

三.对称二叉树

OJ链接：对称二叉树

这道题依旧是递归的思想

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
{
    if(root1==NULL&&root2==NULL)
    return true;//如果两个都是空树，就说明这个结点是对称的

    if(root1==NULL||root2==NULL)
    return false;//上面的if已经排除了两个都是空树的情况，如果这个成立，说明必有一个不是空树，则就是不对称的

    if(root1->val!=root2->val)
    return false;//两棵树都不是空树，就比较它们的值，注意不能用两值相等作为判断条件，因为如果相等就返回的话，后面的结点就比不了了

    return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
    //最后就递归，左树的左子树要跟右树的右子树相等，左树的右子树要跟右树的左子树相等
}
bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left,root->right);
}

注意看注释。

四.二叉树的前序遍历

OJ题目链接：二叉树的前序遍历

看一下我上一篇博客理解了，这个相对于其他的OJ是比较简单的：

/**
 * 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().
 */
 int TreeSize(struct TreeNode* root)//这个函数用来返回树里的全部结点个数
 {
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
 }
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) {
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));//右多少个结点我们就开多少的空间
    int i=0;
    PreOrder(root,a,&i);//前序遍历
    return a;//把数组返回
}

五.相同的树

OJ链接：相同的树

这个其实就跟上面的那个对称二叉树有异曲同工之妙，只是换了一下对比的方向。看一下上面的代码，这个也就十分的好理解。

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);
}

六.另一棵树的子树

OJ链接：另一棵树的子树

注意一下这个题是在上一个判断相同的树的基础上去做的

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

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)//如果树为NULL就不可能是子树
    return false;
    if(root->val==subRoot->val&&isSameTree(root,subRoot))//判断一下根的值相不相等，如果相等判断一下这两个树是不是一样的
    return true;
    
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);//然后在这里开始遍历
}

七.二叉树的构建及遍历

OJ链接：二叉树的构建及遍历

这道题就是把二叉树的构建和遍历整合到一起

#include <stdio.h>
#include<stdlib.h>
typedef struct BTNode
{
    struct BTNode* left;
    struct BTNode* right;
    char val;
}BTNode;
BTNode* CreatTree(char* a,int* pi)
{
    if(a[*pi]=='#')//如果是#就说明这个结点为空树
    {
        (*pi)++;//数组往后走
        return NULL;
    }
    BTNode* root=(BTNode*)malloc(sizeof(BTNode));//动态开辟一块内存
    root->val=a[(*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->val);
    InOrder(root->right);
}
int main()
{
    char a[100];
    scanf("%s",a);
    int i=0;
    BTNode* root=CreatTree(a, &i);
    InOrder(root);
    return 0;
}

这个就是这个题的过程。

如果只看上图不能理解的话看一下下面的代码遍历：

八.二叉树的销毁

二叉树的销毁就十分简单了，只需要记住一个点，因为我们要用到递归，根要放到最后销毁，如果提前销毁了就会导致找不到左右子树。

void BTDestory(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BTDestory(root->left);
    BTDestory(root->right);
    free(root);
}

九.判断二叉树是否为完全二叉树（层序遍历）

解决这个题我们用层序遍历的话会很好写。

首先先说一下层序遍历：

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

简单的说，我们遍历的顺序是这样的：

要实现这个，我们可以用一下队列。

先构建结构体二叉树：

typedef struct BTNode
{
    struct BTNode* left;
    struct BTNode* right;
    char val;
}BTNode;

这个是队列的实现:

特别注意一下第一行的代码，我构建的队列里面的值是指针

typedef struct BTNode* QDataType;

typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType a;
}QNode;
typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* pcur = pq->phead;
    while (pcur)
    {
        QNode* next = pcur->next;//把下一个节点提前保存起来
        free(pcur);
        pcur = next;//指针往后移动
    }
    pq->phead = pq->ptail = NULL;//全部释放完毕后注意指针也要置为NULL
    pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("QueuePush::malloc");
        return;
    }
    newnode->a = x;
    newnode->next = NULL;
    if (pq->ptail == NULL)
    {
        pq->phead = pq->ptail = newnode;
    }
    else
    {
        pq->ptail->next = newnode;
        pq->ptail = pq->ptail->next;
    }
    pq->size++;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->size != 0);
    // 一个节点
    if (pq->phead->next == NULL)
    {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else // 多个节点
    {
        QNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }

    pq->size--;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->phead);
    return pq->phead->a;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->size == 0;
}

然后就是正式的层序遍历：

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);//初始化队列
    if (root)//如果根不为空，就入队列里面
        QueuePush(&q, root);
    while (!QueueEmpty(&q))//循环是等到队列完全没有值了跳出循环
    {
        BTNode* front = QueueFront(&q);//提出队头的值
        QueuePop(&q);//删除队头
        printf("%d ", front->val);//打印二叉树的根结点的值
        if (front->left)//如果左子树不为空，就把左子树入到队列里
            QueuePush(&q, front->left);
        if (front->right)//同理，如果右子树不为空，就把右子树入到队列里
            QueuePush(&q, front->right);
    }
    QueueDestroy(&q);
}

知道了层序遍历，我们就可以做这道题目了：

我们知道，关于完全二叉树它的最后一层的结点一定是顺序存放的。所以我们就可以利用层序遍历往后走，即使遇到空也进队列。当我们遇到第一个空结点时，我们就开始判断，如果后面全是空这棵树就是完全二叉树，反之不是。

bool BTComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)//如果刚好是一个完全二叉树，那么这里为NULL了就说明所有的结点都遍历完毕
        {
            break;//直接跳出循环
        }
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while (!QueueEmpty(&q))//这个循环就是用来判断后面有没有非空节点，有的话就不是完全二叉树
    {
        BTNode* front = QueueFront(&q);
        if (front)//进入这个if语句就说明找到了非空的结点，就不是完全二叉树
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

可以带入图看一下：