二叉树相关的题，判断二叉树是否是单值二叉树，相同的树，对称二叉树，另一棵树的子树，KY11 二叉树遍历

判断二叉树是否是单值二叉树

965. 单值二叉树

单值二叉树，所有结点的值都相同的二叉树即为单值二叉树，判断某一棵二叉树是否是单值二叉树的一般步骤如下：
 1.判断根的左孩子的值与根结点是否相同。
 2.判断根的右孩子的值与根结点是否相同。
 3.判断以根的左孩子为根的二叉树是否是单值二叉树。
 4.判断以根的右孩子为根的二叉树是否是单值二叉树。
若满足以上情况，则是单值二叉树。

//判断二叉树是否是单值二叉树
bool isUnivalTree(BTNode* 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);//左子树是单值二叉树并且右子树是单值二叉树
}

100. 相同的树

100. 相同的树

判断两棵二叉树是否相同，也可以将其分解为子问题：
 1.比较两棵树的根是否相同。
 2.比较两根的左子树是否相同。
 3.比较两根的右子树是否相同。

//判断两棵二叉树是否相同
bool isSameTree(BTNode* p, BTNode* 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);//两棵树的左子树相同并且右子树相同，则这两棵树相同
}

101. 对称二叉树

对称二叉树

要判断某二叉树是否是对称二叉树，则判断其根结点的左子树和右子树是否是镜像对称即可。

因为是镜像对称，所以左子树的遍历方式和右子树的遍历方式是不同的，准确来说，左子树和右子树的遍历是反方向进行的。

如下图

图中红蓝轨迹同时进行，同时结束。若在遍历过程中发现镜像对称的某两个结点值不同，则无需继续遍历，此时已经可以判断该树不是对称二叉树，只有当红蓝轨迹成功遍历完毕后，才能断定该树是对称二叉树。

代码：

//判断镜像位置是否相等
bool travel(BTNode* left, BTNode* right)
{
	if (left == NULL&&right == NULL)//红蓝轨迹同时遍历到NULL，函数返回
		return true;
	if (left == NULL || right == NULL)//红蓝指针中，一个为NULL，另一个不为NULL，即镜像不相等
		return false;
	if (left->val != right->val)//红蓝指针指向的结点值不同，即镜像不相等
		return false;
	//子问题：左子树遍历顺序：先左后右，右子树遍历顺序：先右后左。若两次遍历均成功，则是对称二叉树
	return travel(left->left, right->right) && travel(left->right, right->left);
}
//对称二叉树
bool isSymmetric(BTNode* root)
{
	if (root == NULL)//空树是对称二叉树
		return true;
	return travel(root->left, root->right);//判断镜像位置是否相等
}

572. 另一棵树的子树

572. 另一棵树的子树

判断 subRoot 是否是二叉树 root 的子树，即检验 root 中是否包含和 subRoot 具有相同结构和结点值的子树，其中 root 和 subRoot 均为非空二叉树。

思路：
 依次判断以 root 中某一个结点为根的子树是否与subRoot相同。

实际上，当发现 root 中的某一个子树与 subRoot 相匹配时，便不再继续比较其他子树，所以图中只会比较到序号2就结束比较了。

//比较以root和subRoot为根结点的两棵树是否相等
bool Compare(BTNode* root, BTNode* subRoot)
{
	if (root == NULL&&subRoot == NULL)//均为空树，相等
		return true;
	if (root == NULL || subRoot == NULL)//一个为空另一个不为空，不相等
		return false;
	if (root->val != subRoot->val)//结点的值不同，不相等
		return false;
	//比较两棵树的子结点
	return Compare(root->left, subRoot->left) && Compare(root->right, subRoot->right);
}
//另一个树的子树
bool isSubtree(BTNode* root, BTNode* subRoot)
{
	if (root == NULL)//空树，不可能是与subRoot相同（subRoot非空）
		return false;
	if (Compare(root, subRoot))//以root和subRoot为根，开始比较两棵树是否相同
		return true;
	//判断root的左孩子和右孩子中是否有某一棵子树与subRoot相同
	return isSubtree(root->left, subRoot) || isSubtree(root->right,subRoot);
}

KY11 二叉树遍历

KY11 二叉树遍历

思路：
 根据前序遍历所得到的字符串，我们可以很容易地将其对应的二叉树画出来

其实很容易发现其中的规律，我们可以依次从字符串读取字符：
 1.若该字符不是#，则我们先构建该值的结点，然后递归构建其左子树和右子树。
 2.若该字符是#，则说明该位置之下不能再构建结点了，返回即可。

构建完树后，使用中序遍历打印二叉树的数据即可。

代码：

#include <iostream>
using namespace std;

typedef struct TreeNode {
    struct TreeNode* left;
    struct TreeNode* right;
    char data;
} TreeNode;

int i = 0;
//创建树
TreeNode* CreateTree(string& s)
{
    if(s[i] == '#')
    {
        i++;
        return nullptr;
    }
    //不是NULL，构建结点
    TreeNode* root = new TreeNode;
    root->left = nullptr;
    root->right = nullptr;
    root->data = s[i++];
    //递归构建左子树
    root->left = CreateTree(s);
    //递归构建右子树
    root->right = CreateTree(s);
    return root;
}

void Inorder(TreeNode* root) {
    if (root == nullptr)
        return;
    Inorder(root->left);
    cout << root->data << ' ';
    Inorder(root->right); 
}

int main() {
    string s;
    cin >> s;
    TreeNode* root = CreateTree(s);
    Inorder(root);
    return 0;
}