leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历等的介绍

文章目录

前言
一、单值二叉树
二、相同的树
三、二叉树的前序遍历
四、二叉树的中序遍历
五、二叉树的后序遍历
六、另一棵树的子树
七、二叉树的遍历
总结

前言

leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历等的介绍

一、单值二叉树

leetcode原题：单值二叉树

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
        return true;
    
    if(root->left != NULL && root->left->val != root->val )
        return false;
    
    if(root->right != NULL && root->right->val != root->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

递归思想：
每个节点都分别与它的左子树根节点和右子树根节点比较。
若传入的节点为NULL，返回 true。（不违反相同的规则）
若左右子树分别不为空并且分别不等于根节点则返回 false。

二、相同的树

leetcode原题：相同的树

在这里插入图片描述

/**
 * 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)
    {
        return true;
    }

    if(p == NULL && q != NULL || p != NULL && q == NULL)
    {
        return false;
    }




    if(p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

递归思想：
两棵树同时按照根节点，左子树，右子树的顺序比较每个节点。
若两个树根节点都为NULL，则返回true。
若两棵树根节点只有一个为NULL，则返回false。
若两棵树根节点的值不相等，则返回false。

三、二叉树的前序遍历

leetcode原题：二叉树的前序遍历

其中returnSize是数组元素的个数。传入的是数组元素个数的指针。
要求返回一个数组。

在这里插入图片描述

/**
 * 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 TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void preorder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
        return;
    
    a[(*pi)++] = root->val;
    preorder(root->left, a, pi);
    preorder(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);

    int* a = (int*)malloc(*returnSize * sizeof(int));

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

    return a;
}

思想：
先求出这个树的节点个数，赋值给returnSize。
动态申请returnSize个空间，同时定义下标变量。
在函数preorder中采用前序遍历，将每个节点的值依次赋值给数组。

四、二叉树的中序遍历

leetcode原题：二叉树的前序遍历

在这里插入图片描述

/**
 * 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 TreeSize(struct TreeNode* root)
{
    return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void inorder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
        return;
    
    inorder(root->left, a, pi);
    a[(*pi)++] = root->val;
    inorder(root->right, a, pi);
}


int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);

    int* a = (int*)malloc(*returnSize  * sizeof(int));

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

    return a;
}

五、二叉树的后序遍历

leetcode原题：二叉树的中序遍历

在这里插入图片描述

/**
 * 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 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;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);

    int* a = (int*)malloc(*returnSize * sizeof(int));

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

    return a;
}

六、另一棵树的子树

leetcode原题：另一棵树的子树

在这里插入图片描述

/**
 * 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)
        return true;
    
    if(p== NULL || q == NULL)
        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 == NULL)
        return false;

    if(isSameTree(root, subRoot))
    {
        return true;
    }

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

将原二叉树与给定子树进行比较。
若相同返回true。
若不同，原二叉树的左子树和右子树分别与给定子树比较。有一个相同则返回true。

七、二叉树的遍历

牛客网原题: 二叉树的遍历

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

typedef char BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType val;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

BTNode* preorder(char* arr, int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
        

    BTNode* root = (BTNode*)malloc(sizeof(BTNode));

    root->val = arr[(*pi)++];
    root->left = preorder(arr, pi);
    root->right = preorder(arr, pi);

    return root;
}

void Inorder(BTNode* root)
{
    if(root == NULL)
        return;

    Inorder(root->left);
    printf("%c ", root->val);
    Inorder(root->right);
}

int main() {
    char arr[100] = {0};
    scanf("%s", arr);

    int i = 0;
    BTNode* root = preorder(arr, &i);

    Inorder(root);
    return 0;
}