二叉树OJ练习题（C语言版）

���录

 一、相同的树

 二、单值二叉树

 三、对称二叉树

 四、树的遍历

前序遍历

中序遍历

后序遍历

 五、另一颗树的子树

 六、二叉树的遍历

 七、翻转二叉树

 八、平衡二叉树

 一、相同的树

链接：100. 相同的树 - 力扣（LeetCode）

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

• 首先考虑比较时节点为空的情况，当比较到二者节点都为空时，则当前二者节点相同，返回true。
• 二者节点只有一个为空时， 当前二者节点不相同，返回false。
• 然后考虑不为空时，判断二者的值是否相等，不相等返回false。
• 最后递归调用比较二者当前节点的左子树和右子树，都为true则返回true。

   二、单值二叉树

  链接：965. 单值二叉树 - 力扣（LeetCode）

  bool isUnivalTree(struct TreeNode* root) {    if (root == NULL)        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);}

  • 首先判断当前节点是否为空，如果为空则返回true。
  • 如果当前节点不为空，则判断其左右子树的值是否与当前节点的值相同，如果不同则返回false。
  • 如果左右子树的值都与当前节点的值相同，则递归判断左右子树是否为同值二叉树，即左右子树的所有节点的值都相同。
  • 这个递归过程会一直往下遍历到叶子节点，如果所有节点的值都相同，则返回true，否则返回false。

     三、对称二叉树

    思路：左子树的左节点与右子树的右节点比较，左子树的右节点和右子树的左节点比较

    bool _isSymmetric(struct TreeNode* leftRoot, struct TreeNode* rightRoot) {    if (leftRoot == NULL && rightRoot == NULL)        return true;    if (leftRoot == NULL || rightRoot == NULL)        return false;    if (leftRoot->val != rightRoot->val)        return false;    return _isSymmetric(leftRoot->left, rightRoot->right)         && _isSymmetric(leftRoot->right, rightRoot->left);}bool isSymmetric(struct TreeNode* root) {    return _isSymmetric(root->left, root->right);}

    OJ是允许我们额外根据需要创建函数的，原函数的参数只有一个，不能满足同时判断两个节点的是否相等的要求，所以我们创建递归函数_isSymmetric()，用来判断左右子树是否对称。

    • 如果左右子树都为空，说明对称，返回true；
    • 如果左右子树只有一个为空，说明不对称，返回false；
    • 如果左右子树的值不相等，说明不对称，返回false；
    • 否则，递归判断左子树的左子树和右子树的右子树是否对称，以及左子树的右子树和右子树的左子树是否对称，如果都对称，返回true，否则返回false。
    • 函数isSymmetric()则是调用_isSymmetric()函数，传入根节点的左子树和右子树，判断整个二叉树是否对称。

       四、树的遍历

      前序遍历

      链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

      int TreeSize(struct TreeNode* root) {    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void _preorder(struct TreeNode* root, int* a, int* i) {    if (root == NULL)        return;    a[(*i)++] = root->val;    _preorder(root->left, a, i);    _preorder(root->right, a, i);}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;}

      题中要求我们将前序遍历的结果存到数组中并输出数组，那么我们需要创建一个数组插入数据，同时我们也需要数组的大小，所以我们增加了

      • TreeSize函数统计树的节点个数，
      • _preorder递归函数将节点插入数组。

         preorderTraversal函数中：

        • 首先将TreeSize统计的树的大小赋值给returnSize。
        • 为指针a开辟数组所需的空间，用于存放数组元素。
        • 整型变量 i 用于记录数组当前的索引。
        • 调用_preorder函数对数组进行插入数据。
        • 返回数组a。

           _preorder函数中：

          • 如果当前节点为空，则结束函数。
          • 否则，将当前节点的值插入数组中，每次插入结束后，数组的索引值加一。
          • 这里索引参数为指针类型，用于接收索引 i 的地址，这样才能在函数中及时更新索引值。
          • 递归调用_preorder函数对当前节点的左节点进行处理。
          • 左节点处理后，递归调用_preorder函数对当前节点的右节点进行处理。 

            中序遍历

            94. 二叉树的中序遍历 - 力扣（LeetCode）

            int TreeSize(struct TreeNode* root) {    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void _inorder(struct TreeNode* root, int* a, int* i) {    if (root == NULL)        return;    _inorder(root->left, a, i);    a[(*i)++] = root->val;    _inorder(root->right, a, i);}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;}

            后序遍历

            145. 二叉树的后序遍历 - 力扣（LeetCode）

            int TreeSize(struct TreeNode* root) {    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void _postorder(struct TreeNode* root, int* a, int* i) {    if (root == NULL)        return;    _postorder(root->left, a, i);    _postorder(root->right, a, i);    a[(*i)++] = 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;}

            五、另一颗树的子树

            链接：572. 另一棵树的子树 - 力扣（LeetCode）

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

            调用 isSameTree 辅助判断子树是否相等：

            • 首先考虑比较时节点为空的情况，当比较到二者节点都为空时，则当前二者节点相同，返回true。
            • 二者节点只有一个为空时， 当前二者节点不相同，返回false。
            • 然后考虑不为空时，判断二者的值是否相等，不相等返回false。
            • 最后递归调用比较二者当前节点的左子树和右子树，都为true则返回true。

               isSubtree函数：

              • 如果 root 是 NULL，那么它不可能包含任何子树，函数返回 false。
              • 如果 isSameTree(root, subRoot) 返回 true，说明在当前的节点上，root 和 subRoot 完全相同，那么 subRoot 当然是 root 的子树，函数返回 true。
              • 如果当前节点不匹配，那么递归地在 root 的左子树和右子树中查找 subRoot。
              • 如果 subRoot 是 root 左子树或右子树的子树，函数就返回 true。

                 六、二叉树的遍历

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

                我们需要根据给出的先序(前序)遍历反推出树的样子，例如下图，我们可以动手试一试：

                好的，如果你已经熟悉如何根据遍历反推二叉树的形状，那么试着推出题中的遍历的吧。

                 注意：这道题需要写出主函数，并不像力扣提供接口。

                首先我需要创建二叉树的结构体和相关函数：

                #include #include typedef int BTDataType;typedef struct BinaryTreeNode{    BTDataType data;    struct BinaryTreeNode* left;    struct BinaryTreeNode* right;}BTNode;BTNode* BuyNode(BTDataType x){    BTNode* node=(BTNode*)malloc(sizeof(BTNode));    if(node==NULL){        perror("malloc fail");        return NULL;    }    node->data=x;    node->left=node->right=NULL;    return node;}

                然后进行二叉树的创建：

                • 该函数接收两个参数，一个是字符串a，另一个是指向整型变量i的指针，用于记录当前处理到字符串a的哪个位置。
                • 当前位置数组元素为 # 表示元素值为空，更新数组索引到下一个位置，返回NULL
                • 当前位置元素不为空则为其开辟空间，为树创建新节点，更新数组索引到下一个位置。
                • 递归调用CreateTree函数分别创建该节点的左右子树。
                • 最后返回该节点的指针。

                  在main函数中：

                  • 先定义了一个字符数组a，用于存储输入的字符串，
                  • 然后调用CreateTree函数创建二叉树，将根节点的指针赋值给root，
                  • 最后调用InOrder函数对二叉树进行中序遍历，并输出换行符。

                    BTNode* CreateTree(char* a,int* i){    if(a[*i]=='#'){        (*i)++;        return NULL;    }    BTNode* root=BuyNode(a[*i]);    (*i)++;    root->left=CreateTree(a, i);    root->right=CreateTree(a, i);    return root;}void InOrder(BTNode* root){    if(root==NULL)        return;    InOrder(root->left);    printf("%c ",root->data);    InOrder(root->right);}int main() {    char a[1000];    scanf("%s",a);    int i=0;    BTNode* root=CreateTree(a,&i);    InOrder(root);    printf("\n");    return 0;}

                     七、翻转二叉树

                    链接：226. 翻转二叉树 - 力扣（LeetCode）

                    truct TreeNode* invertTree(struct TreeNode* root) {    if(root==NULL)        return NULL;    struct TreeNode* left=invertTree(root->left);    struct TreeNode* right=invertTree(root->right);    root->left=right;    root->right=left;    return root;}

                    •  如果当前节点为空，则返回NULL.
                    • 否则，递归调用函数对左右子树进行处理，递归到二叉树最底部，从最底部往上进行翻转。
                    • 将节点的左节点赋值为右节点，右节点赋值为左节点，
                    • 最后返回根节点。

                      八、平衡二叉树

                      链接：110. 平衡二叉树 - 力扣（LeetCode）

                      第一种：求出左右子树高度进行判断比较。

                      • height函数用于计算二叉树的高度，它采用递归的方式计算左右子树的高度，然后返回左右子树高度的较大值加1，表示当前节点的高度。

                      • isBalanced函数则是用于判断二叉树是否平衡，它首先判断当前节点是否为空，如果为空则返回true，否则通过 abs 函数计算左右子树的高度差的绝对值，如果高度差大于1，则返回false，否则递归判断左右子树是否平衡。

                        int height(struct TreeNode* root){     if(root == NULL)    return 0;    int leftHeight = height(root->left);    int rightHeight = height(root->right);    return leftHeight > rightHeight ?       leftHeight + 1 : rightHeight + 1;}bool isBalanced(struct TreeNode* root) {    if (root == NULL) {        return true;    }    int leftHeight = height(root->left);    int rightHeight = height(root->right);    if (abs(leftHeight - rightHeight) > 1) {        return false;    }    return isBalanced(root->left) && isBalanced(root->right);}

                         第二种与第一种功能方法一样，但这种方式更简洁

                        同样首先写出求树高度的函数，但这里使用三目运算符使函数更简洁。（fmax返回两个参数中较大的那个。）

                        int maxDepth(struct TreeNode* root){    return root ? 1 + fmax(maxDepth(root->left) , maxDepth(root->right)) : 0;      }bool isBalanced(struct TreeNode* root){    if(root == NULL)        return true;    int left = maxDepth(root->left);    int right = maxDepth(root->right);    return abs(left - right) left)        && isBalanced(root->right);}