二叉树OJ题目合集(单值、对称、平衡、构建加遍历)-Toy模板网

这篇具有很好参考价值的文章主要介绍了二叉树OJ题目合集(单值、对称、平衡、构建加遍历)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

一：单值二叉树

二：二叉树遍历

核心点

(1)前序

(2)中序

(3)后序

三：判断两颗树是否相同

四：判断二叉树是否对称

五：判断一颗树是否为另一颗树的子树

六：平衡二叉树

七：二叉树的构建加遍历

前言：

这一部分适合已经适用于已经掌握二叉树基础的同学(遍历，求节点数等)。

不清楚的同学可以先看之前一期：

https://blog.csdn.net/2301_76269963/article/details/130231257?spm=1001.2014.3001.5502

一：单值二叉树

题目链接：https://leetcode.cn/problems/univalued-binary-tree/submissions/

题目要求：

基础思路：

(1)首先判断根节点值与左右子树值是否相同，如果不同就返回 false。(注意如果左右子树为空不需要进行判断)

(2)否则，递归判断其左右子树是否为单值二叉树。(空树算作单值二叉树)

(3)如果一直到叶子节点都没有出现不相同的节点值，则返回 true，表示该树为单值二叉树。

(左子树右子树同时为单值树才行)

(这个题目比较简单，不利用递归也可以实现，但是需要建立辅助栈，只要遍历所有节点依次判断，遇到不同返回false，遍历完都没有不同返回true)

代码：文章来源地址https://www.toymoban.com/news/detail-433040.html
bool isUnivalTree(struct TreeNode* root)
{
    if(root == NULL)
    {
        return true;
    }

    if(root->left!=NULL && root->left->val != root->val)
    {
        return false;
    }

    if(root->right!=NULL && root->right->val != root->val)
    {
        return false;
    }

    return isUnivalTree(root->left) && isUnivalTree(root->right);

}
图解:

二：二叉树遍历

核心点

(1)我们知道在函数调用时候形参只是实参的临时拷贝，如果我们直接传值调用，是没办法直接与那个变量建立联系的。

(2)如果我们想让函数不管递归深度多大都始终使用一个变量，我们应该进行传址调用。

(1)前序

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/

题目要求：

思路：

①和我们之前的打印不同，这一次遍历是要把节点数据存入数组中

②先求节点数(之前一次讲过)，依据节点数来开辟空间

③先存储数据，再递归走左子树，后递归走右子树，每一次存储完成都要让(*i)加1(本体加1)

④记得为(*returnSize)赋值数组元素个数，告知元素个数，别人才能进行测试

代码：
//求树的节点数
int BinaryTreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

void _preorderTraversal(struct TreeNode* root,int* a,int* i)
{
    if(root == NULL)
    {
        return;
    }
    //赋值
    a[*i] = root->val;
    *i+=1;
    //左子树
    _preorderTraversal(root->left,a,i);
    //右子树
    _preorderTraversal(root->right,a,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    //申请空间存储数据
    int size=BinaryTreeSize(root);
    int* a=(int*)malloc(sizeof(int)*size);

    //遍历存储数据（利用子函数）
    int i=0;
    _preorderTraversal(root,a,&i);

    //返回
    *returnSize = size;
    return a;
}

(2)中序

题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/

题目要求：

二叉树OJ题目合集(单值、对称、平衡、构建加遍历)

思路：与前序基本一致，只是换了存储的顺序

代码：

//求树的节点数
int BinaryTreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

void _inorderTraversal(struct TreeNode* root,int* a,int* i)
{
    if(root == NULL)
    {
        return; 
    }
    
    _inorderTraversal(root->left,a,i);
    a[*i] = root->val;
    *i += 1;
    _inorderTraversal(root->right,a,i);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    //申请空间存储数据
    int size = BinaryTreeSize(root);
    int* a = (int*)malloc(sizeof(int)*size);
    
    //调用子函数存储
    int i=0;
    _inorderTraversal(root,a,&i);

    //返回
    *returnSize = size;
    return a;
}