二叉树OJ题（单值树、相同树、找子树、构建和遍历）

单值二叉树

题目描述

解题思路

这道题理解起来很简单，循环递归将根节点与左右孩子比较，当根结点的值与左右孩子相等时(左右孩子结点同时为空或者其中一个为空另一个不为空结点值与根相同也算相等)，继续递归它的左右孩子，当递归到空结点时返回true，因为空结点也可以算作单值二叉树。
但是这里直接判断根结点与左右孩子结点若相等则返回true有点难写，我们采用正难则反，若孩子结点不为空并且孩子结点的值与根结点不同返回false，否则程序继续往下执行循环递归，只有当根结点的左右子树都为单值二叉树时，才return true。

代码

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        //空结点是单值二叉树
        return true;
    }
    if(root->left && root->val != root->left->val)
    {
        return false;
    }
    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    //当前根节点所对应的树为单值二叉树，继续递归它的左右子树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

相同的树

题目描述

解题思路

这道题思路和上一题有点类似，也是要用正难则反，只有当两个二叉树的结构与值都相等才是相同的树，所以要分别比较两颗二叉树的每一个对应结点，比如比较p的左孩子和q的左孩子。
首先比较结点结构，当两个结点都为空返回true，若其中一个非空返回false，结构判断完后再判断结点的值，当两个结点的值不同返回false，当前面都判断完后程序还在继续执行说明两个结点都不为空且结构与值都相同，就可以继续递归判断根结点的左右孩子结点。

代码

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 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->right) && isSameTree(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root) {
    return isSameTree(root->left, root->right);
}

另一颗树的子树

题目描述

解题思路

这道题也很好理解，但是有一个很恶心的点，当在root里找到一个和subRoot的根结点值相同的结点时，如果该root里的结点所在的二叉树和subRoot不相同时，还需要继续遍历root的剩下结点。
所以这里最好不要findx，而是挨个遍历root里的每一个结点和subRoot比较，当遍历到NULL时一定不会和subRoot相同，所以返回false,当左右子树中有其中一边返回true，则整体返回true。

代码

 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)
    {
        return false;
    }
    if(isSameTree(root, subRoot))
    {
        return true;
    }
    //结构相同+值相同，继续递归左右子树
    return isSubtree(root->left, subRoot) 
    || isSubtree(root->right, subRoot);
}

前序遍历

题目描述

解题思路

在讲解这道题之前小编想想讲一下这里函数的第二个参数，其实在C语言OJ题中这样类似的题目有很多，因为我们只是写了一个接口函数，写的函数需要打包到远程服务器来运行，服务器几乎不会看你的代码逻辑，它只会看最后结果对不对，因为这道题我们需要返回一个数组，这里的returnsize就是用来记录数组长度的，方便服务器直接遍历结果数组，而且returnsize还是传的指针，目的就是让形参的改变也能影响实参。
说回这道题目本身，思路和我们上一篇博客介绍的前序遍历一样，只不过这里不是直接打印出遍历的结点数据，而是把数据保存到数组中，所以首先要求二叉树结点个数，动态开辟一个二叉树结点个数大小的数组，注意这里的数组下标i也要传指针，这样形参的改变才会影响实参。

如果数组下标我们不传指针，比如说下面这颗二叉树，当在结点1的函数栈帧中时，会将数据1存到arr[0]中，之后i++变成1，然后进入结点2的函数栈帧，它会把数据2存到arr[1]中，然后i++变成2，然后退出结点2的函数栈帧来到结点1的函数栈帧中，但是注意，因为在结点2的函数栈帧中i++后是形参i的改变，所以退回到结点1的函数栈帧中后实参i的值还是1，所以后面进入结点3的函数栈帧时i的值还是1，这样就发生数据覆盖了。

中序和后续遍历代码和思路类似，小编就不一一列举了。

代码

typedef struct TreeNode TreeNode;

 int treesize(TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return 1 + treesize(root->left) + treesize(root->right);
 }

void preOrder(TreeNode* root, int* arr, int* pi)
{
    if(root == NULL)
    {
        return;
    }
    //将数据存入数组
    arr[*pi] = root->val;
    (*pi)++;

    preOrder(root->left, arr, pi);
    preOrder(root->right, arr, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    //求二叉树结点个数
    *returnSize = treesize(root);
    //动态申请数组空间
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    //前序遍历二叉树并将数据存入数组
    int i = 0;
    preOrder(root, arr, &i);

    return arr;
}

二叉树的构建及遍历

题目描述

解题思路

这道题需要我们自己定义二叉树结点，自己读取终端数据并输出结果。
首先要读取终端的字符串，所以先创建一个字符数组，把输入的数据保存到字符数组中。
然后根据字符数据构建二叉树，这里也要循环递归来构建，还需要一个数组下标i来遍历字符数组，当遇到’#‘时就要returnNULL，注意return之前要把i++，若遇到有效字符就先创建一个存放该有效字符的结点，再从左到右依次循环递归构建结点，在递归之前要先把i++。
最后根据二叉树结构使用中序遍历递归打印每一个结点。

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* BuyNode(char x)
{
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if(node == NULL)
    {
        perror("malloc");
        exit(1);
    }
    node->val = x;
    node->left = node->right = NULL;
    return node;
}

TreeNode* CreatNode(char* arr, int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode* node = BuyNode(arr[*pi]);
    (*pi)++;
    node->left = CreatNode(arr, pi);
    node->right = CreatNode(arr, pi);
    return node;
}

void inOrder(TreeNode* root)
{
    if(root ==  NULL)
    {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->val);
    inOrder(root->right);
}

int main() {
    //读取前序遍历字符串
    char arr[100];
    scanf("%s", arr);
    //根据字符串创建二叉树结构
    int i = 0;
    TreeNode* root = CreatNode(arr, &i);
    //输出中序遍历结果
    inOrder(root);
    return 0;
}

二叉树选择题

小编先介绍一个二叉树的性质：

第一题根据上面我们介绍的结论很容易得出答案应该为200。
第二题关键词是完全二叉树，完全二叉树有个性质：度为一的结点个数只有两种可能取值：0或1，我们把0和一分别代入表达式，值为整数的就是答案，选A。
第三题要用到满二叉树结点个数与高度的关系，选B。
第四题和第二题类似，选B。

这几道题都是根据遍历结果还原二叉树，这里我们要先知道一个结论，当我们知道了一颗二叉树的中序遍历和前序/后序任意一个，都可以还原二叉树，前提是必须要有中序遍历。
其实解决这类问题都有一个统一的思路，先通过前序或者后序求根结点，前序遍历的第一个结点为根结点，后序遍历的最后一个结点为根结点，然后在中序遍历里找根节点，根节点的左边所有结点为它结构上左子树的所有结点，根节点的右边所有结点为它结构上右子树的所有结点，依次类推可以从最大的二叉树推到最小的二叉树，这样就还原出了整颗二叉树。
答案为A A D A

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的赞和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~