【Java数据结构】二叉树详解（三）
【Java数据结构】二叉树详解（三）
1.❤️❤️前言~🥳🎉🎉🎉
Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪
上篇文章我们讲完二叉树的基本知识点后，这篇文章将会给大家讲解一些二叉树的习题。
2. 检查两颗树是否相同
📌题目描述
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
📋题目思路
首先，判断 p 和 q 是否为 null，如果有且只有一个为 null，则说明两棵树不相同，直接返回 false。如果两个树都不为 null，再判断它们的节点值是否相等，如果不相等则返回 false。如果相等则之后递归比较两个树的左右子树是否相同，如果都相同则返回 true，但凡有不同则直接返回false。
⏳题目代码
//检查两颗二叉树是否相同。
public boolean isSameTree(BTNode p, BTNode q) {
if ((p != null && q == null) || (p == null && q != null))
return false;
if (p != null && q != null) {
if (p.value != q.value)
return false;
}
if (p == null && q == null)
return true;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}该题链接：检查两棵树是否相同
3. 另一颗树的子树
📌题目描述
给你两棵二叉树
root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。 二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
📋题目思路
实现一个函数为isSubtree，用于判断二叉树 root 是否包含和 subRoot 具有相同结构和节点值的子树。 具体来说，首先调用一个我们在第一题中已经实现的函数 isSameTree（已经实现过该函数了，在这就不说了），判断 root 和 subRoot 是否完全相同（即结构和节点值都相同）。若相同则返回 true，否则继续递归调用isSubtree函数去判断 root 的左右子树中是否包含和 subRoot 相同的子树。只要有一个子树满足条件即可返回 true。若遍历完整个树仍未找到相同的子树，则返回 false。
⏳题目代码
//给你两棵二叉树 root 和 subRoot 。
//检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
//如果存在，返回 true ；否则，返回 false 。
public boolean isSubtree(BTNode root, BTNode subRoot) {
if (isSameTree(root, subRoot))
return true;
if (root != null)
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
return false;
}
public boolean isSameTree(BTNode p, BTNode q) {
if ((p != null && q == null) || (p == null && q != null))
return false;
if (p != null && q != null) {
if (p.value != q.value)
return false;
}
if (p == null && q == null)
return true;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
该题链接：另一颗树的子树
4.翻转二叉树
📌题目描述
给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点。
📋题目思路
具体步骤为：
- 首先判断当前节点是否为空，如果为空则返回null。
- 判断当前节点的左右子树是否都为空，如果不都为空，则交换左右子树。
- 递归反转左子树。
- 递归反转右子树。
- 最后返回反转后的二叉树的根节点。
⏳题目代码
//给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
public BTNode invertTree(BTNode root) {
if (root == null)
return null;
if (root.left != null || root.right != null) {
BTNode temp = root.right;
root.right = root.left;
root.left = temp;
}
if (root.left != null)
invertTree(root.left);
if (root.right != null)
invertTree(root.right);
return root;
}该题链接：翻转二叉树
5.对称二叉树
📌题目描述
给你一个二叉树的根节点
root， 检查它是否轴对称。
📋题目思路
具体实现方法为： 首先判断二叉树的根节点是否为null，若为null则返回true，因为空树是对称的。 接着调用check函数，该函数的参数是二叉树的左右子树。 在check函数中，首先判断左右子树是否都为null，若是则返回true；若有一个为null而另一个不是，则返回false，因为左右子树不对称。 若左右子树都不为null，则判断它们的值是否相等，若不相等则返回false。 最后，递归调用check函数判断左子树的左子树和右子树的右子树是否对称，以及左子树的右子树和右子树的左子树是否对称，若都对称则返回true，否则返回false。
⏳题目代码
//给你一个二叉树的根节点 root,检查它是否轴对称。(用了两个方法)
public boolean isSymmetric(BTNode root) {
if (root == null)
return true;
return check(root.left, root.right);
}
public boolean check(BTNode rootLeft, BTNode rootRight) {
if (rootLeft == null && rootRight == null)
return true;
if ((rootLeft == null && rootRight != null) || (rootLeft != null && rootRight == null))
return false;
return (rootLeft.value == rootRight.value)
&& check(rootLeft.left, rootRight.right)
&& check(rootLeft.right, rootRight.left);
}该题链接：对称二叉树
6.判断一颗二叉树是否是平衡二叉树
📌题目描述
给定一个二叉树，判断它是否是 平衡二叉树
6.1第一种思路
📋题目思路
实现一个判断二叉树是否为平衡二叉树的方法。该方法接收一个 BTNode 类型的参数 root，表示二叉树的根节点，返回一个 boolean 类型的值，表示该二叉树是否为平衡二叉树。 首先判断当前节点是否为 null，若为 null 则返回 true，因为空树也可以看作是平衡二叉树。接着分别计算当前节点左右子树的高度，通过递归调用 getHeight 方法实现。最后判断当前节点的左右子树的高度差是否小于等于 1，若是则继续递归判断其左右子树是否为平衡二叉树，若均为平衡二叉树，则返回 true；否则返回 false。 注意：该代码在递归过程中，每个节点会被遍历多次，所以会出现重复计算的情况。经过优化后可以通过，大大缩短运行时间，优化后的方法就是第二种思路方法
⏳题目代码
/*
给定一个二叉树，判断它是否是平衡二叉树
平衡二叉树 :是指该树所有节点的左右子树的深度相差不超过1。
*/
public boolean isBalanced(BTNode root) {
if(root==null)
return true;
int a=getHeight(root.left);
int b=getHeight(root.right);
return Math.abs(a-b)<=1 && isBalanced(root.left)&&isBalanced(root.right);
}
int getHeight(BTNode root) {
int height = 0;
if (root == null)
return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}6.2第二种思路
📋题目思路
具体实现过程如下 首先，判断二叉树是否为空。若为空，则认为其是平衡的，返回 true。否则，调用 getHeight() 函数计算二叉树的高度。 getHeight() 函数递归地计算二叉树的高度。若当前节点为空，则返回 0。否则，分别递归计算左右子树的高度，并判断其高度差是否小于等于 1。若满足条件，则返回左右子树中更高的高度加一。否则，返回 -1，表示当前子树不平衡。 如果返回出的二叉树高度大于0，则认为是平衡的；否则认为是不平衡的。 第二种思路相比第一种思路其运行时间大大缩短了，可以说比第一种思路更好，直接一次遍历就实现了效果
⏳题目代码
//给定一个二叉树，判断它是否是平衡二叉树.(进阶版，更加高效)
public boolean isBalanced(BTNode root) {
if(root==null)
return true;
if(getHeight(root)>0)
return true;
else
return false;
}
public int getHeight(BTNode root){
if(root==null)
return 0;
int a=getHeight(root.left);
if(a<0)
return -1;
int b=getHeight(root.right);
if(b<0)
return -1;
if(Math.abs(a-b)<=1)
return Math.max(a,b)+1;
else
return -1;
}
}该题链接：判断一颗二叉树是否是平衡二叉树
7.二叉树的构建及遍历
📌题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）， 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
📋题目思路
这题比较难，我们讲的细致些，并且对于该题没有帮我们自动实现内部类，我们需要自己去实现。以下是对这段代码的详细讲解：
类和成员变量
public class Main{
public int i; // 用于追踪当前处理的字符位置
static class BTNode{
char value; // 节点的值
BTNode left; // 左子节点
BTNode right; // 右子节点
public BTNode(char value) {
this.value = value;
}
}
}Main类包含一个成员变量i，用于记录当前处理的字符位置。BTNode是一个静态内部类，表示二叉树的节点。每个节点包含一个字符值（value），一个指向左子节点的指针（left），和一个指向右子节点的指针（right）。
主函数
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
Main main = new Main(); // 为每行输入创建一个新的Main对象
String b = in.nextLine(); // 读取一行输入
BTNode root = main.creatBinaryTree(b); // 构建二叉树
main.inOrder(root); // 对构建的二叉树进行中序遍历
System.out.println(); // 输出完一行后换行
}
}- 主函数使用
Scanner对象从标准输入中读取用户输入的字符串。 while (in.hasNextLine())循环可以处理多行输入。- 对于每一行输入，创建一个新的
Main对象并调用creatBinaryTree方法构建二叉树，然后调用inOrder方法进行中序遍历并输出结果。
构建二叉树
public BTNode creatBinaryTree(String s){
if (i >= s.length()) {
return null;
}
if (s.charAt(i) == '#') {
return null;
}
BTNode root = new BTNode(s.charAt(i)); // 创建根节点
i++;
root.left = creatBinaryTree(s); // 递归构建左子树
i++;
root.right = creatBinaryTree(s); // 递归构建右子树
return root;
}creatBinaryTree方法通过递归的方式根据前序遍历字符串构建二叉树。- 如果当前字符是
#，表示当前节点为空，返回null。 - 否则，创建一个新节点，并递归构建左子树和右子树。
- 需要注意的是，
i在递归调用前后都会自增，以确保处理下一个字符。
中序遍历
public void inOrder(BTNode root){
if (root == null)
return;
inOrder(root.left); // 递归遍历左子树
System.out.print(root.value + " "); // 打印当前节点的值
inOrder(root.right); // 递归遍历右子树
}inOrder方法通过递归的方式进行中序遍历。- 如果当前节点为空，直接返回。
- 先递归遍历左子树，再打印当前节点的值，最后递归遍历右子树。
代码中的潜在问题
i的初始值：i应该在每次构建新树前初始化为0，以确保从字符串的开始位置处理。所以我们将i设置为实例成员变量，这样每次创建新树时i初始值都是0。.- 字符串边界检查：在访问字符串字符前需要检查索引是否越界，一般我们输入的字符串都是合法的，不会发生越界情况。
⏳题目代码
/*编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。*/
public class Main{
public int i;
static class BTNode{
char value;
BTNode left;
BTNode right;
public BTNode(char value) {
this.value = value;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
Main main=new Main();
String b = in.nextLine();
BTNode root = main.creatBinaryTree(b);
main.inOrder(root);
}
}
public BTNode creatBinaryTree(String s){
if(s.charAt(i)=='#')
return null;
BTNode root =new BTNode(s.charAt(i));
i++;
root.left= creatBinaryTree(s);
i++;
root.right=creatBinaryTree(s);
return root;
}
public void inOrder( BTNode root){
if(root==null)
return;
inOrder(root.left);
System.out.print(root.value+" ");
inOrder(root.right);
}
}该题链接：二叉树的构建及遍历
8.总结
这篇文章讲了6个二叉树习题，下篇文章将会继续讲二叉树的相关习题。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏
腾讯云开发者
