小码农二叉树OJ淬体 二叉树OJ淬体

发表于

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

二叉树OJ淬体

例1：单值二叉树

题目

image-20211114094938096

image-20211114100001843 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码bool isUnivalTree(struct TreeNode* root){
    //空树直接就是单值
    if(!root)
        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);
}

例2：二叉树的前序遍历

题目

image-20211114101027475

image-20211114211340327 

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
c复制代码//我们先把二叉树的节点个数求出来
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)
        return;
    a[(*i)++] = root->val;
    _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);
    //我们直接递归preorderTraversal它，是不好递归的因为每次递归你都开辟一个数组吗，不现实
    //我们应该递归他的类似性质的函数，不过不可以次次开辟数组，应该传递数组再给一个下标
    int i = 0;
    _preorderTraversal(root,a,&i);
    *returnSize = size;
    return a;
}

例3：二叉树的中序遍历

题目

image-20211116214530749

image-20211116214359131 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
c复制代码 //二叉树节点个数函数
int BinaryTreeSize(struct TreeNode* root){
    if(!root)
        return 0;
    return BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
//子函数
void _inorderTraversal(struct TreeNode* root,int* a,int* pi){
    if(!root)
        return;
    _inorderTraversal(root->left,a,pi);
    a[(*pi)++] = root->val;
    _inorderTraversal(root->right,a,pi);   
}
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;
}

例4：二叉树的后序遍历

题目

image-20211116214847981

image-20211116221210027 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码//二叉树
int BinaryTreeSize(struct TreeNode* root){
    return root == NULL ? 0 : BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
//子函数
void _postorderTraversal(struct TreeNode* root,int* a,int* pi){
    if(!root)
        return;
    _postorderTraversal(root->left,a,pi);
    _postorderTraversal(root->right,a,pi);
    a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    //数组大小传过来
    int size = BinaryTreeSize(root);
    //创建合适的数组
    int* a = (int*)malloc(sizeof(int)*size);
    int i = 0;
    _postorderTraversal(root,a,&i);
    *returnSize = size;
    return a;
}

例5：相同的树

题目

image-20211114214742547

image-20211114233423560 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //都为空
    if(!p && !q)
        return true;
    //有且只有一个是空
    if(!p || !q)
        return false;
    //没有空树
    if(p->val != q->val)
        return false;
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

例6：对称二叉树

题目

image-20211116072024229

image-20211116073040713 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
c复制代码bool _isSymmetricTree(struct TreeNode* root1,struct TreeNode* root2)
{
    //两个都是空就返回真
    if(!root1 && !root2)
        return true;
    //只有一个空直接假
    if(!root1 || !root2)
        return false;
    if(root1->val != root2->val)
        return false;
    return _isSymmetricTree(root1->left,root2->right) 
        && _isSymmetricTree(root1->right,root2->left);
}

bool isSymmetric(struct TreeNode* root){
    //空树就是对称
    if(!root)
        return true;
    //返回他们判断结果    
    return _isSymmetricTree(root->left,root->right);
}

例7：另一棵树的子树

题目

image-20211116074903027

image-20211116202318803 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码 //判断是否是相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //都为空
    if(!p && !q)
        return true;
    //有且只有一个是空
    if(!p || !q)
        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)
        return false;
    if(isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)
        || isSubtree(root->right,subRoot); 
}

例8：二叉树遍历

题目

image-20211118001943031

image-20211118231042018 

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
55
56
c复制代码#include <stdio.h>
#include <stdlib.h>

//树节点
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* right;
    struct BinaryTreeNode* left;
    int val;
}BTNode;

//创建树
BTNode* CreateTree(char* str,int* pi)
{
    //#就返回空
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    //不是空开始建树
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->val = str[(*pi)++];
    //递归创建
    root->right = CreateTree(str,pi);
    root->left = CreateTree(str,pi);
    return root;
}
//中序遍历
void InOrder(BTNode* root)
{
    //空就返回
    if(!root)
        return;
    //先走左
    InOrder(root->right);
    //打印中
    printf("%c ",root->val);
    //再走右
    InOrder(root->left);
}

int main()
{
    //因为不超过100
    char str[100] = {0};
    //多组输入
    while(scanf("%s",str) != EOF)
    {
        //创建树
        int i = 0;
        BTNode* root = CreateTree(str,&i);
        InOrder(root);
    }    
    return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%