二叉树OJ习题

bool isUnivalTree(struct TreeNode* root) {
    //判断节点是否为空
    if(root==NULL)
    {
        return true;
    }
    //左孩子存在并且值不等于其父节点值时，返回false
    if(root->left && root->left->val != root->val)
    {
        return false;
    }
    //右孩子存在并且值不等于其父节点值时，返回false
    if(root->right && root->right->val != root->val)
    {
        return false;
    }
    //递归左右子树，只有都为单值二叉树时，返回false
    return isUnivalTree(root->left) && isUnivalTree(root->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 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->right) && isSameTree(p->right,q->left);
}

bool isSymmetric(struct TreeNode* root) {
    return isSameTree(root->left,root->right);
}

typedef struct TreeNode TreeNode;
bool isSameTree(TreeNode* p,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);
}

 typedef struct TreeNode TreeNode;

//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//前序遍历
//传下标的指针，在递归过程中能够改变
void PreOrder(TreeNode* root,int* arr,int* pi)
{
    if(root==NULL)
    {
        return;
    }
    arr[(*pi)++]=root->val;
    PreOrder(root->left,arr,pi);
    PreOrder(root->right,arr,pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    //*returnSize表示数组元素个数,也就是二叉树节点个数
    *returnSize = BinaryTreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    PreOrder(root,arr,&i);
    return arr;
}

typedef struct TreeNode TreeNode;

//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{
    if(root==NULL)
    {
      return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//传下标的指针，在递归过程中能够改变
void InOrder(TreeNode* root,int* arr,int* pi)
{
      if(root==NULL)
      {
        return;
      }
      InOrder(root->left,arr,pi);
      arr[(*pi)++]=root->val;
      InOrder(root->right,arr,pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    //*returnSize表示数组元素个数,也就是二叉树节点个数
    *returnSize = BinaryTreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    InOrder(root,arr,&i);
    return arr;
}

typedef struct TreeNode TreeNode;

//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//传下标的指针，在递归过程中能够改变
void PostOrder(TreeNode* root,int* arr,int* pi)
{
    if(root==NULL)
    {
        return;
    }
    PostOrder(root->left,arr,pi);
    PostOrder(root->right,arr,pi);
    arr[(*pi)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    //*returnSize表示数组元素个数,也就是二叉树节点个数
    *returnSize=BinaryTreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    //按后序遍历将二叉树中的数据存储在数组
    int i=0;
    PostOrder(root,arr,&i);
    return arr;
}

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

//定义二叉树节点结构
typedef struct BinaryTreeNode{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

//申请新节点
BTNode* buyNode(char x)
{
    BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
    if(newnode==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data=x;
    newnode->left=newnode->right=NULL;

    return newnode;
}

//构建二叉树
BTNode* creatBinaryTree(char* arr,int* pi)
{
    if(arr[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root=buyNode(arr[(*pi)++]);
    root->left=creatBinaryTree(arr, pi);
    root->right=creatBinaryTree(arr, pi);

    return root;
}

//中序遍历
void InOrder(BTNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}

int main() {
    //输入字符串存储起来
    char arr[100];
    scanf("%s",arr);
    //按前序遍历构建二叉树
    int i=0;
    BTNode* root = creatBinaryTree(arr, &i);
    //中序遍历
    InOrder(root);
    return 0;
}