编号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的值 并没有改变
上面之所以没有问题的原因是因为二叉树是一颗单边树 它只有左边或者只有右边
这么这里修改下代码
将所有的传值调用都改成传址调用
然后
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
