数据结构-二叉树（2）

作者：学Java的冬瓜
博客主页：☀冬瓜的主页🌙
专栏：【C/C++ 数据结构和算法】

前言

今天的这篇博客，主要是二叉树的相关习题，包括笔试选择题，OJ题。对于二叉树的基本概念、求二叉树的特征，二叉树的性质，请看上一篇博客。

链接：
上篇博客：二叉树的基本概念及基本特征的求法

一、二叉树遍历选择题

1、前序+中序=》二叉树

2、后序+中序=》二叉树

二、OJ题

LeetCode题

题1：二叉树的前序遍历

链接：
LeetCode144.二叉树的前序遍历

法一：利用指针计算返回数组大小

int TreeSize(struct TreeNode* root)
{
    return root==NULL? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}

void _PrevOrder(struct TreeNode* root, int* a, int* pi)
{
    if(root==NULL)
    {
        return;
    }

    a[*pi] = root->val;
    (*pi)++;

    _PrevOrder(root->left, a, pi);
    _PrevOrder(root->right, a,pi);
}

//注意1：下面的struct TreeNode* root是输入型参数，int* returnSize是输出型参数
//因为只返回a不确定这个数组到底有多大，所以再设置一个输出型参数。
//达到返回两个数据的作用，从而确定空间的大小
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{    
    //注意2：先计算这棵树的节点个数，从而确定数组大小
    int size=TreeSize(root);
    
    int* a = (int*)malloc(size*sizeof(int));
    
    //注意3：防止每次递归都创建a空间，所以不调用自己，另外用一个函数实现递归遍历
    int i=0;
    _PrevOrder(root, a, &i);
    
    //注意4：设置输出型参数，返回两个数据，从而确定数组大小
    *returnSize=i;
    return a;
}
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

法二：利用全局变量计算数组大小

注意：
1、因为有多组测试用例，每次使用完全局变量，都需要置0。
2、如果用局部变量统计数组个数，那么递归中归的时候i是上一层的i，而不是下一层计算过后的i。

int TreeSize(struct TreeNode* root)
{
    return root==NULL? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}

int i=0;
void _PrevOrder(struct TreeNode* root, int* a)
{
    if(root==NULL)
    {
        return;
    }

    a[i] = root->val;
    i++;

    _PrevOrder(root->left, a);
    _PrevOrder(root->right, a);
}


int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //注意重点1：因为有多组测试用例，所以用全局变量统计数组元素个数
    //在每一个用例使用完后，这个全局变量都需要置0
    i=0;

    int size=TreeSize(root);
    int* a = (int*)malloc(size*sizeof(int));

    _PrevOrder(root, a);

    *returnSize=i;
    return a;
}
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

题2：二叉树的中序遍历

链接：
LeetCode94.二叉树的中序遍历

说明：和前序遍历一样，用了指针计算数组大小，然后去访问

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void _PrevOrder(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
        return;


    _PrevOrder(root->left, a, pi);

    a[*pi] = root->val;
    (*pi)++;

    _PrevOrder(root->right, a, pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = TreeSize(root);
    int* a = (int*)malloc(size * sizeof(int));

    int i = 0;
    _PrevOrder(root, a, &i);

    *returnSize = i;
    return a;
}
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

题3：二叉树的后序遍历

链接：
LeetCode145.二叉树的后序遍历

说明：和前序遍历一样，用了指针来表示数组大小，然后去访问

int TreeSize(struct TreeNode* root)
{
    return root==NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void _PostOrder(struct TreeNode* root, int* a, int* pi)
{
    if(root==NULL)
        return;

    _PostOrder(root->left, a, pi);
    _PostOrder(root->right, a, pi);

    a[*pi] = root->val;
    (*pi)++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);
    int* a = (int*)malloc(size*sizeof(int));

    int i=0;
    _PostOrder(root, a, &i);

    *returnSize = i;
    return a;
}
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

题4：平衡二叉树

链接：
LeetCode110.平衡二叉树

说明：平衡二叉树通俗来讲就是这棵树的节点分布均匀。在规律上：
一棵平衡二叉树，每个结点的左右子树的高度差的绝对值不超过1。

思路：

1. 从根节点开始判断，左右子树的高度差，不大于1，然后再进入子树的检查
2. 遇到NULL前全都符合高度差不大于1，则开始归。如果高度差大于1，那么直接层层返回false
3. 如果递归完都符合，那就是到了最开始的根节点处的return那一行，都为真。即return true。完全符合条件。

int maxDepth(struct TreeNode* root)
{
    if(root==NULL)
        return 0;

    int leftdepth = maxDepth(root->left);
    int rightdepth = maxDepth(root->right);

    return leftdepth>rightdepth ? leftdepth+1 : rightdepth+1;
}

//判断是否是平衡二叉树：需要计算当前节点的左右子树的高度差是否小于2，然后利用分治原理
bool isBalanced(struct TreeNode* root){
    //注意3：
    //1>当从树的根节点检查到叶节点都符合条件，
    //然后检查到叶节点的下一层为NULL，那么这棵子树是符合条件的
    //2>如果最开始的根节点root==NULL，那也是返回true
    if(root==NULL)
        return true;

    //注意1：当前节点不为空，就计算它的左右子树高度差
    int leftdepth = maxDepth(root->left);
    int rightdepth = maxDepth(root->right);

    //注意2：判断左右子树的高度差是否符合条件
    //不符合就直接返回false，符合条件则进入递归，进行子树的检查
    return (abs(leftdepth-rightdepth) < 2 
    && isBalanced(root->left) 
    && isBalanced(root->right));
}
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

牛客题

题5：二叉树的遍历

链接：
牛客.二叉树的遍历

要求：根据前序遍历(+#表示空)的字符串，创建二叉树，并完成中序遍历

思路：

1. 用pi(传址调用)来作为字符串下标，防止字符归时重复访问。
2. 先判断当前字符，不是#，开始创建树的节点，然后该节点的left和right=递归创建树函数，开始进入递归。
3. 每次当前节点的左右子树都创建完(以NULL为叶子节点的left和right)后。就返回当前节点，让上一层的调用来接收。
4. 如果遇到了#，说明这棵树在这个节点的方向已经完成，return NULL，让上一层调用接收。

#include 
#include 

typedef char TDataType;
typedef struct TreeNode
{
    TDataType val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

//重点1：
//创建二叉树，要用到递归，除了传二叉树的根节点，还要用pi(统计)来保证str字符串在归时
//str指针指向的字符不会回到之前的字符
//从而保证一个一个字符的访问，每个字符只访问一次
TreeNode* CreatTree(char* str, int* pi)
{
    //重点5：当遇到字符#时，表示上一个节点的当前子树为NULL
    //完成最开始的递归中的递,然后归，然后可能递可能归。
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    //重点2：当str字符串当前字符为有效字符(不为#)时，创建树的节点，
    //并把当前字符赋值给节点的val
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    if(root==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    
    root->val = str[*pi];
    (*pi)++;
    
    //重点3：创建新的节点后，开始进入递归，创建这个节点的左右子树
    root->left = CreatTree(str, pi);
    root->right = CreatTree(str, pi);
    
    //重点4：当前这个节点及其左右子树创建完成后，返回该节点
    return root;
}

void InOrder(TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}

int main()
{
    char str[100];
    scanf("%s",str);
    int i = 0;
    TreeNode* tree = CreatTree(str, &i);
    InOrder(tree);
    return 0;
}
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
57
58
59
60
61
62
63
64
65
66

最后：大家国庆快乐啊！今天女篮虽然没有打赢，但她们站在赛场上的那一刻，我就觉得已经是胜利了，真的很棒！希望祖国更加繁荣富强，也希望大家都越来越好！