刷爆leetcode第十期 0021~0022
编号0021 单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
题目图片如下
我们这里主要是判断下 根的值和它的左孩子还有右孩子相不相等
如果相等返回true 如果不相等返回false
（当然这里还需要考虑一个问题 就是左右孩子可能为空的问题 ）
当左右孩子为空的时候 返回true
我们首先写出以下代码
// 如果root为空就直接返回ture
if(root==NULL)
{
return true;
}
//后面判断不相等的条件 因为判断相等的条件要判断多次
if(root->left && root->left->val == root ->val)
{
}
我们来看这里
第二个判断条件中
如果左值不为空 且左值等于右值
这个时候能判断是真还是假了嘛？
显然不能 这时候还需要判断右值 还需要判断空的情况
所以说我们这么写
if(root->left && root->left->val != root ->val)
这样子写 如果这个条件成立的话就可以直接返回假了
接下来只要再判断下右边值还有后面的就可以
代码表示如下
bool isUnivalTree(struct TreeNode* root)
{
// 如果root为空就直接返回ture
if(root==NULL)
{
return true;
}
//后面判断不相等的条件 因为判断相等的条件要判断多次
if(root->left && root->left->val != root->val)
{
return false;
}
if(root->right && root->right->val != root->val)
{
return false;
}
//判断完根之后再判断它的左值右值
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
编号0022 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
题目图如下
这里结合过我们之前学过的前序遍历
它其实是一个很简单的问题
但是这里要注意的有两点
第一点 关于开辟动态内存大小的问题 我们可以先算出二叉树节点的个数
这个很简单 直接贴代码
int size(struct TreeNode* root)
{
//先看边界条件
if(root==NULL)
{
return 0;
}
// 接下来递归下面的值
return size(root->left)+ size(root->right)+1;
}
第二点 关于递归的问题
这里我们不能在主函数中递归
我们来看看主函数中设定了哪些值
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
// 判断二叉树有多少节点
int size1 = size(root);
//开辟动态内存并且设立i作为数组下标
int* arr = (int* )malloc(sizeof(int)*size1);
int i = 0;
如果在主函数中递归的话 那么就会不断的开辟新的动态内存导致错误
而且会重置i的值
好了 我们写完的代码全部表示如下
/**
* 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 size(struct TreeNode* root)
{
//先看边界条件
if(root==NULL)
{
return 0;
}
// 接下来递归下面的值
return size(root->left)+ size(root->right)+1;
}
void _preorderTraversal(struct TreeNode* root, int* arr , int i )
{
//开始前序遍历
if(root==NULL)
{
return ;
}
arr[i++] = root->val;
// 遍历左子树和右子树
_preorderTraversal(root->left,arr,i);
_preorderTraversal(root->right,arr,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
// 判断二叉树有多少节点
int size1 = size(root);
//开辟动态内存并且设立i作为数组下标
int* arr = (int* )malloc(sizeof(int)*size1);
int i = 0;
// 因为我们在主函数里面不可以递归调用 这样会开始很多个a数组的空间
_preorderTraversal(root,arr,i);
//设定返回值
//printf("%d",size1);
*returnSize = size1;
return arr;
}
我们来测试下代码
咦 我们发现 这里出错了
最后面一个数是随机值！！
这是为什么呢？
我们检查下代码
终于 我们找到了以下代码
void _preorderTraversal(struct TreeNode* root, int* arr , int i )
我们这里传递的i是一个值 再经过递归之后实际上是拷贝了一份i的值
真正i的值 并没有改变
上面之所以没有问题的原因是因为二叉树是一颗单边树 它只有左边或者只有右边
这么这里修改下代码
将所有的传值调用都改成传址调用
然后
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯