😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏：数据结构
🔊本专栏主要更新的是数据结构部分知识点
💪种一棵树最好是十年前其次是现在

目录

1.单值二叉树 

2.相同的树

3.前序遍历

4.另一棵树的子树

5.二叉树遍历

1.单值二叉树 

题目链接：力扣

​

 代码演示：

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

2.相同的树

题目链接：力扣

​

• 思路：首先如果p,q都是空，那么满足条件，直接返回true。如果其中一个为空，则返回false；如果两个都不为空，这个时候还应该分两种情况，如果对应的值不等，那么返回false，如果相等则继续递归比较它们的左右子树。
• 代码实现：

  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.前序遍历

题目链接：力扣

• 思路：在上篇文章我们已经实现了前序遍历，而此题明显就是让我们去模拟实现，题中条件明确指出要动态开辟一块数组来存放数据，关键是开辟多大空间呢？所以这里用到第一个辅助函数——求节点个数函数(TreeSize)。接下来就是依次递归分治思想，但是我们发现了一个致命的缺陷，就是每次递归到主函数时都要malloc，这样是十分消耗栈帧的，因此还需要构造第二个辅助函数专门用于递归。
• 注意点：传节点个数时，一定要传地址。因为每次递归都会建立栈帧，递归完就会销毁，无法保存。此外，*returnSize是要返回数组元素的，返回给调用者。
• 代码演示：

  //写一个函数用于求出二叉树节点的个数，方便后面malloc
  int TreeSize(struct TreeNode* root)
  {return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
  }//写一个专门用于递归的函数，防止用主函数递归时每次都要malloc
  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;//i一定要传地址，因为每次递归都会建立栈帧，递归完之后就会销毁preorder(root,a,&i);return a;
  }

4.另一棵树的子树

题目链接：力扣

• 思路：遍历左边树的每一个节点使其作为子树的根，跟右树的子树都比较一下，此时就可以cv之前写过的函数(isSameTree) ，用来比较两棵树是否相同，依次比较，如果是子树，则返回true
• 代码演示：

  //判断两棵树是否相同
  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;//是子树就返回true}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
  }

   

5.二叉树遍历

题目链接：二叉树遍历_牛客题霸_牛客网

•  思路：首先本题要求根据我们输入的字符串将其构建成树，再按照中序的遍历方式输出。例如：
•  构造时要按照先序遍历，递归过程如下：首先遇到a，不是‘#’，接着向下构造左子树b，同理再向下构造左子树c，这个时候遇到了‘#’。则回溯到c，再来构造c的右子树，结果又遇到‘#’，因此再向上回溯到b，此时再构造b的右子树，接着同理……
• 如果已经创建好二叉树的结构了，下面只需要按照中序遍历打印出来即可。
• 代码演示：

  //创建二叉树结构
  struct TreeNode
  {struct TreeNode* left;struct TreeNode* right;char val;
  };//创建节点，先序结构创建
  struct TreeNode* CreatTree(char* a,int* pi)
  {if(a[*pi]=='#'){(*pi)++;return NULL;}struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));root->val=a[(*pi)++];root->left=CreatTree(a,pi);root->right=CreatTree(a,pi);return root;
  }//中序输出
  void InOrder(struct TreeNode* root)
  {if(root==NULL){return ;}InOrder(root->left);printf("%c ",root->val);InOrder(root->right);
  }int main() {char a[100];scanf("%s",a);int i=0;struct TreeNode* root=CreatTree(a,&i);InOrder(root);return 0;
  }