二叉树习题集_二叉树的题

1.单值二叉树

965. 单值二叉树 - 力扣（LeetCode） (leetcode-cn.com)

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

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)//1.根为空
    {
        return true;
    }
    if(root->left == NULL && root->right == NULL)//2.根不为空，左右孩子为空
    {
        return true;
    }
    if(root->left == NULL)//3.左孩子为空，右孩子不为空
    {
        return root->val == root->right->val//根的值是否等与右孩子 && 右子树是否为单值二叉树
        && isUnivalTree(root->right);
    }
    if(root->right == NULL)//4.右孩子为空，左孩子不为空
    {
        return root->val == root->left->val//根的值是否等与左孩子 && 左子树是否为单值二叉树
        && isUnivalTree(root->left);
    }
    return root->val == root->left->val  //4.左右孩子都不为空
           &&root->val == root->right->val//根是否同时等于左右孩子 && 左右子树均为单值二叉树
           && 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
22
23
24
25
26
27
28
29
30
31
32
33
34

2.相同的树

100. 相同的树 - 力扣（LeetCode） (leetcode-cn.com)

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL && q==NULL)//1.两棵树都是空树
    {
        return true;
    }
    if(p==NULL || q== NULL)//2.其中一棵树为空树
    {
        return false;
    }
    if(p->val!=q->val)//3.两棵树都不是空树但是值不等
    {
        return false;
    }
    //4.两棵树都不是空树且值相等&&对应的左右子树分别是相同的树
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->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

3.对称二叉树

101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)

给你一个二叉树的根节点 root ， 检查它是否轴对称。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool _isSymmetric(struct TreeNode* left, struct TreeNode* right)//子问题
{
    if(left == NULL && right == NULL)//2.1左右均为空
    {
        return true;
    }
    if(left == NULL || right == NULL)//2.2左右其中一个为空，另一个非空
    {
        return false;
    }
    if(left->val != right->val)//2.3左右都不为空且值不等
    {
        return false;
    }
    return  _isSymmetric(left->left, right->right)  //2.4继续判断左的左孩子，右的右孩子 &&
           && _isSymmetric(left->right , right->left);//左的右孩子，右的左孩子

}
bool isSymmetric(struct TreeNode* root){
    if(root==NULL)//1.根为空
    {
        return true;
    }
    return _isSymmetric(root->left, root->right);//2.根不为空转换为子问题

}
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

4.二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

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

int TreeSize(struct TreeNode* root)
{
    return root==NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void _preorderTraversal(struct TreeNode* root, int* arr, int* pi)//为很么传地址，因为这又这样每次递归才是用的同一个'i'
{
    if(root == NULL)  
    {
        return;
    }
    arr[(*pi)++] = root->val;//不为空就把值放在数组里面，然后i++，然后访问左子树，再访问右子树
    _preorderTraversal(root->left, arr, pi);
    _preorderTraversal(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = TreeSize(root);//首先求出二叉树的节点个数
    int* arr = (int*)malloc(sizeof(int)*(*returnSize));//开辟一个数组存放节点的值
    int i = 0;
    _preorderTraversal(root, arr, &i);//为什么要创建子函数，因为我们用到了递归，如果递归原函数，那么每次都会malloc
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode） (leetcode-cn.com)

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL && q==NULL)//1.两棵树都是空树
    {
        return true;
    }
    if(p==NULL || q== NULL)//2.其中一棵树为空树
    {
        return false;
    }
    if(p->val!=q->val)//3.两棵树都不是空树但是值不等
    {
        return false;
    }
    //4.两棵树都不是空树且值相等&&对应的左右子树分别是相同的树
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
//思路就是遍历root，如果subroot是root的子树，那么再遍历过程中一定存在isSameTree函数返回值为真的情况
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    {
        return false;
    }
    if(isSameTree(root, subRoot))
    {
        return true;
    }
    return isSubtree(root->left, subRoot)
           || isSubtree(root->right, subRoot);

}
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

6.二叉树遍历

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
}TreeNode;
TreeNode* TreeCreat(char* str, int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));//构建树根
    root->val = str[*pi];
    (*pi)++;
    root->left = TreeCreat(str, pi);//构建左子树
    root->right = TreeCreat(str, pi);//构建右子树
    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* root = TreeCreat(str, &i);//构建树
    InOrder(root);//中序遍历树
    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