【数据结构】二叉树基础OJ

我就是我 2023-10-13 17:06 45阅读 0赞

**目录**

1. 单值二叉树

2. 检查两颗树是否相同

3. 对称二叉树

4. 二叉树的前序遍历

5. 二叉树的中序遍历

6. 二叉树的后序遍历

7. 另一颗树的子树

8. 二叉树的结构及遍历

--------------------

世界上没有不劳而获的东西！

--------------------

### 1. 单值二叉树 ###

**链接**：[力扣][Link 1]

**代码1**：

/**
     * 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 && root->val != root->left->val)
        {
            return false;
        }
        if (root->right && root->val != root->right->val)
        {
            return false;
        }
        return isUnivalTree(root->left) && isUnivalTree(root->right);
    
    }

**思想**：（1）【左孩子的返回值是否相等+右孩子的返回值是否相等】当左孩子和根比较不相等或者右孩子和根比较不相等，这个树就是不相等的【返回true的条件比较多，所以，返回不相等的条件少】【代码1】（2）遍历，和根的值进行比较

> 注意：（1）在OJ题中尽量不要定义静态变量和全局变量

### 2. 检查两颗树是否相同 ###

**链接**：[力扣][Link 2]

**代码**：

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

**思想**：递归；分治

### 3. 对称二叉树 ###

**链接**：[力扣][Link 3]

**代码**：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
    {
        //
        if (p == NULL && q == NULL)
        {
            return true;
        }
        //其中一个为空
        if (p == NULL || q == NULL)
        {
            return false;
        }
        return p->val == q->val && _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
    }
    
    bool isSymmetric(struct TreeNode* root)
    {
        if (root == NULL)
        {
            return true;
        }
        return _isSymmetric(root->left, root->right);
    
    }

**思想**：首先，判断树的左子树和右子树是否相等；然后，判断左子树的左子树和右子树的右子树以及左子树的右子树和右子树的左子树是否相等，以及重复这个操作

### 4. 二叉树的前序遍历 ###

**链接**：[力扣][Link 4]

**代码**：

/**
     * 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().
     //意思是返回值可以被malloc，假设由调用者释放
     */
    //首先确定二叉树的节点个数
    int BinaryTreeSize(struct TreeNode* root)
    {
        return root == NULL ? 0 : (BinaryTreeSize(root->left)+BinaryTreeSize(root->right) + 1);
    }
    
    int* preorder(struct TreeNode* root, int* a, int* pi)
    {
        if (root == NULL)
        {
            return;
        }
        a[*pi] = root->val;
        (*pi)++;
        preorder(root->left, a, pi);
        preorder(root->right, a, pi);
    }
    
    int* preorderTraversal(struct TreeNode* root, int* returnSize)
    {
        //定义的是数组的指针，因为定义的如果是数组，出了这个函数，就被销毁了
        int size = BinaryTreeSize(root);//j节点个数
        int* a = (int*)malloc(sizeof(int) * size);//定义数组
        if (a == NULL)
        {
            printf("malloc fail\n");
            exit(-1);
        }
        *returnSize = size;
        //前序遍历，并把结果，给数组,
        int i = 0;
        preorder(root,a, &i);
        return a;
    }

**思想**：首先，我们可以非常容易地想到前序遍历的，把之前学到过的前序遍历的printf，改成数组的赋值。看题意，我们需要定义一个数组的指针和二叉树的节点个数，然后尽可以调用前序遍历的函数，进行解决。

> 注意：returnSize 这个代表的是数组的大小，这个函数，相当于输出型参数，returnSize，外面定义了，但是没有值，需要我们对齐进行赋值。【这里应该用指针，因为形参的改变并不影响实参】

### 5. 二叉树的中序遍历 ###

**链接**：[力扣][Link 5]

**代码**：

/**
     * 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 BinaryTreeSize(struct TreeNode* root)
    {
        return root == NULL ? 0 : (BinaryTreeSize(root->left) + BinaryTreeSize(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;
        (*pi)++;
        inorder(root->right, a, pi);
    }
    
    int* inorderTraversal(struct TreeNode* root, int* returnSize)
    {
        int size = BinaryTreeSize(root);
        *returnSize = size;
        int* a = (int*)malloc(sizeof(int) * size);
        if (a == NULL)
        {
            printf("malloc fail\n");
            exit(-1);
        }
        int i = 0;
        inorder(root, a, &i);
        return a;
    }

### 6. 二叉树的后序遍历 ###

**链接**：[力扣][Link 6]

**代码**：

/**
     * 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 BinaryTreeSize(struct TreeNode* root)
    {
       return root == NULL ? 0 : (BinaryTreeSize(root->left) + BinaryTreeSize(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 = BinaryTreeSize(root);
       *returnSize = size;
       int* a = (int*)malloc(sizeof(int) * size);
       int i = 0;
       postorder(root, a, &i);
       return a;
    }

### 7. 另一颗树的子树 ###

**链接**：[力扣][Link 7]

**代码**：

/**
     * 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;
        }
        return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }

**思想**：分治，根中是否有和subRoot相等+左子树中是否有和subRoot相等的部分+左子树中是否有和subRoot相等的部分。

> 注意：主函数中，我们可能会漏掉if这个条件语句，如果不写这个代码，root->left，就会出现问题。

### 8. 二叉树的结构及遍历 ###

**链接**：[牛客][Link 8]

**代码**：

#include <stdio.h>
    #include <stdlib.h>
    typedef struct BinaryTreeNode
    {
        char data;
        struct BinaryTreeNode* left;
        struct BinaryTreeNode* right;
    }BTNode;
    //先构建一个二叉树【前序遍历】
     BTNode* CreatTree(char* a, int* pi)
     {
        if (a[*pi] == '#')
        {
            (*pi)++;
            return NULL;
        }
        //先构建根
        BTNode* root = (BTNode*)malloc(sizeof(BTNode));
        root->data = a[*pi];
        (*pi)++;
        //再构建左子树和右子树
        root->left = CreatTree(a, pi);
        root->right = CreatTree(a, pi);
        return root;
     }
    
    void InOrder(BTNode* root)
    {
        if (root == NULL)
        {
            return;
        }
        InOrder(root->left);
        printf("%c ", root->data);
        InOrder(root->right);
    }
    
    int main()
    {
        char a[100];
        scanf("%s", a);
        int i = 0;
        BTNode* tree = CreatTree(a, &i);
        InOrder(tree);
        free(tree);
        tree = NULL;
        return 0;
    }

**思想**：先序遍历的思想的字符串，建立二叉树【遇到'\#',就返回NULL】，然后再中序遍历的思想进行打印。

[Link 1]: https://leetcode.cn/problems/univalued-binary-tree/submissions/
[Link 2]: https://leetcode.cn/problems/same-tree/
[Link 3]: https://leetcode.cn/problems/symmetric-tree/submissions/
[Link 4]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[Link 5]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[Link 6]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[Link 7]: https://leetcode.cn/problems/subtree-of-another-tree/
[Link 8]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking