单值二叉树
思路：根节点跟左子树比较，若相等则继续比，一值比到左子树为空，比完之后再跟右子树比较
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); }
相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p==NULL&&q==NULL) return true; //如果都为空则返回真 if(p==NULL||q==NULL) return false; //一个为空，一个不为空，则false if(p->val!=q->val) return false;//不相等，fasle return isSameTree(p->left,q->left)&&isSameTree(q->right,p->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(q->right,p->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); }
二叉树的前序遍历
思路：1.先统计出该二叉树节点的个数
2.创建一个新的数组，数组大小为二叉树总结点大小
3.进行前序遍历根，左，右
int TreeSize(struct TreeNode* root) { if(root==NULL) return 0; return TreeSize(root->left)+TreeSize(root->right)+1; } //统计个数 void 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); }//遍历 /** * Note: The returned array must be malloced, assume caller calls free(). */ int* preorderTraversal(struct TreeNode* root, int* returnSize){ int n=TreeSize(root); int *a=(int*)malloc(sizeof(int)*n); int i=0; preorder(root,a,&i); *returnSize=n; return a; }
二叉树的构造及遍历
1.建立一个数组，给数组输入数据，#代表NULL
2.构建一个二叉树，把数组的值输按前序遍历输入到二叉树中，当遇到#时，代表该节点为空
3.将前序遍历好的二叉树，进行中序遍历
#include<stdio.h> #include<stdlib.h> typedef char Datatypedef; typedef struct BinaryTreeNode { Datatypedef data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode;//定义二叉树 TreeNode* CreateTree(char* arr, int* pi) { if (arr[*pi] == '#') { (*pi)++; return NULL; } TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode)); tmp->data = arr[*pi]; (*pi)++; tmp->left = CreateTree(arr, pi); tmp->right = CreateTree(arr, pi); return tmp; }//创建二叉树，并把数组的值赋值给二叉树，按前序遍历赋值 void InorDer(TreeNode* tmp) { if (tmp == NULL) return; InorDer(tmp->left); printf("%c ", tmp->data); InorDer(tmp->right); }//前序遍历换为中序遍历 int main() { char arr[100]; scanf("%s", arr); int i = 0; TreeNode* root = CreateTree(arr, &i); InorDer(root); return 0; }
