c语言-数据结构-二叉树OJ之子树与二叉树的构建

---

前言

二叉树OJ

---

一、另一棵树的子树

题目链接：https://leetcode.cn/problems/subtree-of-another-tree/description/

通过两个示例我们可以看到，子树要求叶子节点也要一模一样，不允许出现根节点和叶节点之间有一棵subRoot树的情况，如示例2

那么本题，我们依然可以沿顺相同树的思路，subRoot是root的子树，不就代表subRoot包含于root吗，那么我们将root中的每一个节点都和root的根节点进行比较，值相同就同时往下走，不同就只走root，最后判断是否存在即可

代码如下：

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

二、二叉树的构建及遍历

题目链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

本题我们需要先根据它给出前序遍历字符串构建出一个完整的二叉树

前序遍历的顺序是根左子树右子树，构建二叉树还是较为简单的

代码如下：

#include <stdbool.h>
#include <stdio.h>
#include<stdlib.h>
typedef char TreeDataType;
typedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;TreeDataType val;
}TreeNode;
TreeNode* SetTree(TreeDataType* a,int* pi)
{if(a[(*pi)] == '#'){(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = a[(*pi)++];root->left = SetTree(a,pi);root->right = SetTree(a,pi);return root;
}
void InOrder(TreeNode* root)
{if(root == NULL){return;}InOrder(root->left);printf("%c ",root->val);InOrder(root->right);
}
int main() {TreeDataType* a;a = (TreeDataType*)malloc(sizeof(TreeDataType) * 100);scanf("%s",a);int i = 0;TreeNode* root = SetTree(a,&i);InOrder(root);return 0;
}