刷爆leetcode第十期 0021~0022

编号0021 单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

题目图片如下

我们这里主要是判断下 根的值和它的左孩子还有右孩子相不相等

如果相等返回true 如果不相等返回false

（当然这里还需要考虑一个问题 就是左右孩子可能为空的问题 ）

当左右孩子为空的时候 返回true

我们首先写出以下代码

    // 如果root为空就直接返回ture
    if(root==NULL)
    {
        return true;
    }
    //后面判断不相等的条件 因为判断相等的条件要判断多次
    if(root->left && root->left->val == root ->val)
    {
        
    }
1
2
3
4
5
6
7
8
9
10

我们来看这里

第二个判断条件中

如果左值不为空 且左值等于右值

这个时候能判断是真还是假了嘛？

显然不能 这时候还需要判断右值 还需要判断空的情况

所以说我们这么写

 if(root->left && root->left->val != root ->val)
1

这样子写 如果这个条件成立的话就可以直接返回假了

接下来只要再判断下右边值还有后面的就可以

代码表示如下

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

编号0022 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

题目图如下

这里结合过我们之前学过的前序遍历

它其实是一个很简单的问题

但是这里要注意的有两点

第一点 关于开辟动态内存大小的问题 我们可以先算出二叉树节点的个数

这个很简单 直接贴代码

int  size(struct TreeNode* root)
{
    //先看边界条件
    if(root==NULL)
    {
        return 0;
    }

    // 接下来递归下面的值
    return size(root->left)+ size(root->right)+1;
}
1
2
3
4
5
6
7
8
9
10
11

第二点 关于递归的问题

这里我们不能在主函数中递归

我们来看看主函数中设定了哪些值

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    // 判断二叉树有多少节点
    int size1 = size(root);

    //开辟动态内存并且设立i作为数组下标
    int* arr = (int* )malloc(sizeof(int)*size1);
    int i = 0;
1
2
3
4
5
6
7
8

如果在主函数中递归的话 那么就会不断的开辟新的动态内存导致错误

而且会重置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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

我们来测试下代码

咦 我们发现 这里出错了

最后面一个数是随机值！！

这是为什么呢？

我们检查下代码

终于 我们找到了以下代码

void _preorderTraversal(struct TreeNode* root, int* arr , int i )
1

我们这里传递的i是一个值 再经过递归之后实际上是拷贝了一份i的值

真正i的值 并没有改变

上面之所以没有问题的原因是因为二叉树是一颗单边树 它只有左边或者只有右边

这么这里修改下代码

将所有的传值调用都改成传址调用

然后

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够

不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯