二叉树的构建及遍历
本题目的要求是：
输入一个数组，里面存放了若干个字符，#代表了空指针，数组中的顺序是
是先序遍历，然后要求你用中序输出
首先我们要做的就是构造结构体：
typedef struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; }TreeNode;
然后用先序遍历构造二叉树
当数组的首元素为#或者“\0”，即二叉树没有根节点，为空树，直接接返回
然后我们开辟新节点的空间
然后进行先序遍历构造二叉树：
首先将newnode的值置为数组首元素，同时下标count++
然后递归newnode的左子树根节点，*（count）++（count传的是地址，所以记得解引用），随后递归右子树根节点即可，最后返回newnode，就是二叉树的根节点
TreeNode* maketree(char*arr,int*count) { if(arr[*count]=='#'||arr[*count]=='\0') { return NULL; } TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode)); newnode->val = arr[(*count)++]; newnode->left = maketree(arr,count); (*count)++; newnode->right = maketree(arr,count); return newnode; }
最后写一个中序遍历的输出：
void Inorder(TreeNode* root) { if(root==NULL) { return; } Inorder(root->left); printf("%c ",root->val); Inorder(root->right); }
完整代码如下：
#include <stdio.h> #include<stdlib.h> typedef struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; }TreeNode; TreeNode* maketree(char*arr,int*count) { if(arr[*count]=='#'||arr[*count]=='\0') { return NULL; } TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode)); newnode->val = arr[(*count)++]; newnode->left = maketree(arr,count); (*count)++; newnode->right = maketree(arr,count); return newnode; } void Inorder(TreeNode* root) { if(root==NULL) { return; } Inorder(root->left); printf("%c ",root->val); Inorder(root->right); } int main() { char arr[101]; scanf("%s",arr); int count = 0; TreeNode* tree = maketree(arr,&count); Inorder(tree); return 0; }
判断一颗二叉树是否是平衡二叉树
本题很简单了：
直接判断左子树和右子树的高度的绝对值是否小于等于1即可
同时左子树的子树和右子树的子树也要同时递归
调用求二叉树高度的函数
int height(struct TreeNode* root) { if(root==NULL) { return 0; } return fmax(height(root->left),height(root->right))+1; } bool isBalanced(struct TreeNode* root) { if(root==NULL) { return true; } return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right); }
另一颗树的子树
本题就是判断一颗树的子树是否是另一棵树
所以我们首先要做的就是构造一个判断两棵树是否相等的函数：
当两个树同时为空时也是相等的
当其中一个为空时肯定时不想同的
当root的值不等于subroot的值时肯定是不相等的
bool issame(struct TreeNode* root,struct TreeNode* subroot) { if(root==NULL&&subroot==NULL) return true; if(root==NULL||subroot==NULL) return false; if(root->val==subroot->val) { if(issame(root->left,subroot->left) &&issame(root->right,subroot->right)) return true; } return false; }
然后调用这个函数：
当root和subroot相等时也符合题意
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root==NULL) return false; if(issame(root,subRoot)) return true; return isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot); }
对称二叉树
其实判断二叉树是否对称就是左边和右边比较，对折重合
即：
左子树和右子树相同，左子树的左子树后右子树的右子树相同
我们直接调用上一题的判断树是否相同的函数
然后拿左子树和右子树比较即可
当左子树的根节点和右子树的根节点不相等时只返回false
bool issame(struct TreeNode* rootleft,struct TreeNode* rootright) { if(rootleft==NULL&&rootright==NULL) return true; if(rootleft==NULL||rootright==NULL) return false; if(rootleft->val==rootright->val) { if(issame(rootleft->left,rootright->right) &&issame(rootleft->right,rootright->left)) return true; } return false; } bool isSymmetric(struct TreeNode* root) { if(root->left==NULL&&root->right==NULL) return true; if(root->left==NULL||root->right==NULL) return false; if(root->left->val==root->right->val) { if(issame(root->left,root->right)) return true; } return false; }
检查两颗树是否相同
这不简简单单，和之前的函数差不多，使用递归就是了
同时为空返回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); }
翻转二叉树
反转二叉树就是把左子树变成右子树，右子树变成左子树
很简单，直接先开辟空间存放，然后赋于即可
struct 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; }
二叉树最大深度
最大深度不就是高度吗，就是层数啊
直接递归，就是左子树和右子树中深度大的那一个+1
int maxDepth(struct TreeNode* root) { if(root==NULL) return 0; return fmax(maxDepth(root->left), maxDepth(root->right)) + 1; }
单值二叉树
单值二叉树就是二叉树所有节点的值都相等
二叉树为空符合题意，返回true
左子树和右子树为空符合题意，只有一个节点，返回true
当有一个不为空时，不为空子树根节点和根节点不相等直接返回false
当两个子树都不为空时判断两个子树的根节点是否相等，不相等直接返回false，然后递归左子树和右子树的根节点
bool isUnivalTree(struct TreeNode* root) { if(root==NULL) return true; if(root->left==NULL&&root->right==NULL) return true; if(root->left==NULL||root->right==NULL) { if(root->left==NULL) { if(root->val!=root->right->val) return false; } if(root->right==NULL) { if(root->val!=root->left->val) return false; } } if(root->left!=NULL&&root->right!=NULL) { if(root->val!=root->left->val||root->val!=root->right->val) return false; } return isUnivalTree(root->left)&&isUnivalTree(root->right); }
好了，今天的分享到这里就结束了，谢谢大家！
