【LeetCode】二叉树基础练习 5 道题
第一题：单值二叉树
题目介绍：
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回true；否则返回false。
//题目框架
bool isUnivalTree(struct TreeNode* root){
}
问题分析：
很多老铁看到这道题，一上来会选择直接遍历二叉树来试图解决这道题。当然遍历固然可行，这道题使用二叉树的前中后遍历的方式来解决，虽然实现的过程存在一定的差异，但都能做出来。
这里给出前序遍历的实现，以便参考。
前序遍历，无非是先判断根节点，在判断左右子树。根节点的值不一样，返回false，左右子树中任何一方存在节点的值不一样都返回false。
bool PreOrderCompare(struct TreeNode* root, int val)
{
if(NULL == root)
{
return true;
}
//先判断根节点
if(val != root->val)
{
return false;
}
//在判断左右子树
return PreOrderCompare(root->left,val) && PreOrderCompare(root->right,val);
}
bool isUnivalTree(struct TreeNode* root)
{
if(NULL == root)
{
return true;
}
//比较后，所有的值都相同返回true;存在有的值不相同返回false.
return PreOrderCompare(root, root->val);
}
但是，我这里想给出另一种非遍历比较的方法。
要判断一棵二叉树的每个结点是否都具有相同的值，只要判断这棵二叉树的根节点、左子树、右子树是否都是相同的值即可。
如果左子树节点的值==根节点的值 并且 右子树节点的值==根节点的值，那么由等式的传递性，就可以知道这棵二叉树是单值二叉树。
所以，可以给出参考代码如下：
bool isUnivalTree(struct TreeNode* root)
{
if(NULL == root)
{
return true;
}
//判断左子树的值是否等于根节点的值
if(root->left!=NULL && root->left->val!=root->val)
{
return false;
}
//判断右子树的值是否等于根节点的值
if(root->right!=NULL && root->right->val!=root->val)
{
return false;
}
//接着从左右子树的根节点开始判断
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
这种比较判断的方法，本质也是利用了类似前序遍历的方式来解决的。
有小伙伴想使用中序遍历或后序遍历来解决这个问题，其实从分析来看是不太好的。
因为，假设整棵树的根节点的值就是那个异同的值，或者异同的值在整棵树比较靠上的层次。中序遍历和后序遍历都是在后来才遍历根节点，需要先去树里面找一圈回来才发现有一个异同的值，这样的话就增加了不必要的遍历。虽然问题能解决，但肯定不是优解。
注意：如果二叉树为空的话，其实并不违背单值二叉树的定义，也就是二叉树中并不存在不相等的值，所以仍然可以把空树看作单值二叉树。以上代码也是如此处理的。
第二题：相同的树
题目介绍：
给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//题目框架
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
}
问题分析：
判断这两棵二叉树是否相同，只要判断根节点相同，并且左右子树相同即可。
但只要根节点，或者左右子树有一个不相同，那就返回false。
同时要注意树是否为空的情况处理。
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//两棵树都为空的情况
if(NULL==p&&NULL==q)
{
return true;
}
//一棵树为空，一棵树不为空的情况
if(NULL==p||NULL==q)
{
return false;
}
//判断根节点
if(p->val!=q->val)
{
return false;
}
//判断左右子树
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
上述代码，仍是以前序遍历的思想来解决的。
第三题：对称二叉树
题目介绍：
给你一个二叉树的根节点root， 检查它是否轴对称。
//题目框架
bool isSymmetric(struct TreeNode* root){
}
问题分析：
从上图中可以看出，二叉树中整棵树的根节点对于判断该二叉树是否对称影响并不大。
所以，如果根节点为空，直接判断它是对称的(其实空树并不违背对称的性质)。
如果整棵二叉树的根节点不为空，就去判断它的左右子树是否符合对称的性质即可。
但是要说明的是，子树中的根节点已经不能像整棵二叉树的根节点那样进行同样的处理了。至于原因看图就懂了😉。
所以，从上面分析之后，我们可以将代码分成两部分来处理。如下面所示。
bool isSymmetricSubTree(struct TreeNode* root1,struct TreeNode* root2)
{
//这两个if用法和《相同的树》代码中的用法是一致的
if(root1==NULL&&root2==NULL)
{
return true;
}
if(root1==NULL||root2==NULL)
{
return false;
}
//根节点值的判断
if(root1->val!=root2->val)
{
return false;
}
//注意：此处因为是进行对称的判断，由镜像对称的性质，可以知道，left和right是镜像对称点，所以传值不要弄错了
return isSymmetricSubTree(root1->left,root2->right) && isSymmetricSubTree(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root)
{
//二叉树的根节点为空
if(NULL==root)
{
return true;
}
//二叉树的根节点不为空
return isSymmetricSubTree(root->left,root->right);
}
第四题：另一棵树的子树
题目介绍：
给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。
二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
root树上的节点数量范围是[1, 2000]
subRoot树上的节点数量范围是[1, 1000]
//题目框架
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
}
问题分析：
认真分析之后会发现，这个题就是是《相同的树》的变相问法。
为什么这么说呢？
其实，要判断subRoot的子树是否在root的树之中，肯定要去root树中去找呀(你这不废话吗😓)。
嘿嘿别急，既然去找，那如何去找呢？答案无非就是遍历了呗。
所以，其实就这么简单。
遍历root的每个节点，并都看做其所在子树的根节点，然后使用《相同的树》的判断方法，去和subRoot所在的子树进行比较。如果相同返回true，遍历完后还没找到，就返回false。
鉴于此，可得如下代码：
//采用前序遍历
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
if(isSameTree(root,subRoot))
{
return true;
}
//左右子树中有一个找到了，就返回true.
return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
第五题：二叉树遍历
说明：这个题是来自牛客网的，在力扣上没能找到，大家见谅了。
题目介绍：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入包括1行字符串，长度不超过100。
问题分析：
这道题归根到底主要在于二叉树的创建。题目给出了二叉树的前序遍历字符串(带空节点），那咱也自然按照前序的方式来建树(此建树非彼建树，哈哈😜)了。
其实大多数的时候也只能是用前序的方式来建立树了。如果没有根节点的话，生成的左右子树节点的地址就不能直接被保存在根节点的指针域中。而将这些地址保存起来，最终放到后来生成的根节点中的话，想想就比较麻烦，不如使用前序遍历来得直接。另外从自然发展的角度来看的话，如果一棵树连根都没有，那它又如何能枝繁叶茂呢。
也就是说，使用先序遍历来建树，先建立根节点，再建立根节点的左子树，再建立根节点的右子树。如果是空节点#，就返回NULL，不是空节点，就返回创建的root节点。
根据此思路，可以给出二叉树前序创建的代码：
//str代表前序遍历的字符串
//pi是记录字符串下标的地址
struct TreeNode* CreateTree(char* str, int* pi)
{
//遇到‘#’，返回NULL
if('#'==str[*pi])
{
(*pi)++;
return NULL;
}
//先创建根节点，在创建左子树，再创建右子树，最后返回根节点
struct TreeNode* root=BuyNode(str[(*pi)++]);
root->left = CreateTree(str,pi);
root->right = CreateTree(str,pi);
return root;
}
好了，通过上面的代码将二叉树创建出来以后，只需再中序遍历一遍，打印输出就OK了。
完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//二叉树节点定义
struct TreeNode
{
char val;
struct TreeNode* left;
struct TreeNode* right;
};
//生成一个节点
struct TreeNode* BuyNode(char c)
{
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
assert(newNode);
newNode->val=c;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
struct TreeNode* CreateTree(char* str, int* pi)
{
if('#'==str[*pi])
{
(*pi)++;
return NULL;
}
struct TreeNode* root=BuyNode(str[(*pi)++]);
root->left = CreateTree(str,pi);
root->right = CreateTree(str,pi);
return root;
}
//中序遍历打印
void InOrderPrint(struct TreeNode* root)
{
if(NULL==root)
{
return;
}
InOrderPrint(root->left);
printf("%c ", root->val);
InOrderPrint(root->right);
}
int main()
{
char str[101]={0};
scanf("%s",str);
int i=0;
struct TreeNode* root = CreateTree(str, &i);
InOrderPrint(root);
return 0;
}