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

文章目录

判断二叉树是否是单值二叉树
100. 相同的树
101. 对称二叉树
572. 另一棵树的子树
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. 相同的树

在这里插入图片描述
判断两棵二叉树是否相同，也可以将其分解为子问题：
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. 另一棵树的子树

在这里插入图片描述

判断 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 二叉树遍历

在这里插入图片描述
思路：
根据前序遍历所得到的字符串，我们可以很容易地将其对应的二叉树画出来

其实很容易发现其中的规律，我们可以依次从字符串读取字符：
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;
}