❣博主主页: 33的博客❣
▶文章专栏分类: Java从入门到精通◀
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构的知识
目录
- 1.前言
- 2.经典习题
- 2.1相同的树
- 2.2另一棵子树
- 2.3翻转二叉树
- 2.4平衡二叉树
- 2.5对称二叉树
- 2.6二叉树的构建及遍历
- 2.7二叉树的分层遍历
- 3.总结
1.前言
在上一篇文章中，博主主要介绍了树与二叉树的基本概念、二叉树概念及特性、遍历方式自己实现一棵二叉树，在这篇文章中，博主将继续与大家分享二叉树经典习题。
2.经典习题
2.1相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同：OJ链接
解题思路
递归思想：
1.如果p为空，q为空，那么就是两颗空树肯定相等
2.如果一个树为空另一棵树不为空那么一定不相等
3.如果都不为空，值相同才相等。
4.在递归判断左子树是否相等，右子树是否相等，只有左右子树都相等才是相同的树
class Solution {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}
//p、q有一个为空
if(p==null&&q!=null||p!=null&&q==null){
return false;
}
//两个都不为空，不相等
if(p.val!=q.val){
return false;
}
//两个都不为空且p=q
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
2.2另一棵子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树：OJ链接
解题思路
递归思想
1.如果其中一个为null那么就不是子树
2.如果是两棵相同的树，那么就为一定为子树
3.再递归看sub是否为左子树的子树，右子树的子树，如果都不是，则返回false
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null &&subRoot!=null|| subRoot == null&&root!=null) {
return false;
}
if(isSameTree(root,subRoot)){
return true;
} if(isSubtree(root.left,subRoot)){
return true;
} if(isSubtree(root.right,subRoot)){
return true;
}
return false;
}
2.3翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树：OJ链接
解题思路
1.判断是否为空树，判断这棵树是否只有根节点
2.再交换左右子树
public TreeNode invertTree(TreeNode root) {
if(root==null||root.left==null&&root.right==null){
return root;
}
TreeNode tmp= root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
2.4平衡二叉树
给定一个二叉树，判断它是否是 平衡二叉树(左右子树相差不超过1)：OJ链接
解题思路
递归思想
1.先求一个树深度
2.求左子树的深度，再求右子树的深度，相差>1则不平衡
3.并且左子树和右子树的每一个个小树都要平衡
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int left=MaxLength(root.left);
int right=MaxLength(root.right);
if (Math.abs(left-right)<=1&&isBalanced(root.right)&&isBalanced(root.left)){
return true;
}else {
return false;
}
}
public int MaxLength(TreeNode root){
if (root==null){
return 0;
}
int Left=MaxLength(root.left);
int Right=MaxLength(root.right);
return Left>Right?Left+1:Right+1;
}
我们观察以上代码，我们发现在求长度的时候已经遍历了一次二叉树，但在求是否平衡的时候，每次递归又会再求高度再遍历数组，效率非常低。那有能不能在求高度的时候就可以判断子树是否平衡呢？答案是可以的，如下：
当求高度的时候先先判断左子树和右子树只差是否小于1，如果小于1就返回-1，就不会再往递归了。
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
return MaxLength(root)>0;
}
public int MaxLength(TreeNode root){
if (root==null){
return 0;
}
int Left=MaxLength(root.left);
int Right=MaxLength(root.right);
if(Left>=0&&Right>=0&&Math.abs(Left-Right)<=1){
return Math.max(Left,Right)+1;
}else return -1;
}
2.5对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称：OJ链接
解题思路
1.判断root是否为null
2.比较左子树和右子树是否对称
3.若其中一棵树为null，那么不对称，若都为null则对称
4.再判断，左子树的左节点是否等于右子树的右节点&&左子树的右节点等于右子树的左节点，依次递归。
class Solution {
public boolean isSymmetric(TreeNode root){
if(root==null){
return true;
}else {
return isSymmetric(root.left,root.right);
}
}
public boolean isSymmetric(TreeNode L,TreeNode R){
if(L==null&&R==null){
return true;
}
if(L==null&&R!=null||L!=null&&R==null){
return false;
}
if(L.val!= R.val){
return false;
}
return isSymmetric(L.left,R.right)&&isSymmetric(L.right,R.left);
}
}
2.6二叉树的构建及遍历
读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树：OJ链接
解题思路
1.遍历字符串，不为#，就new一个Node，但在遍历字符串的时候，我们要把i设置为成员变量防止每次递归后i从0开始
2.遍历二叉树中序输出
class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
static int i=0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String str=in.nextLine();
TreeNode root= createTree(str);
inOrder(root);
}
}
public static TreeNode createTree(String str) {
// for (int i=0;i<str.length();i++) {
// char ch = str.charAt(i);i每次则从0开始
TreeNode root=null;
if(str.charAt(i)!='#'){
root=new TreeNode(str.charAt(i));
i++;
root.left=createTree(str);
root.right=createTree(str);
}else {
i++;//不要担心i超出字符串长度的问题
}
return root;
}
public static void inOrder(TreeNode root){
if(root==null){
return ;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
2.7二叉树的分层遍历
分层遍历二叉树：OJ链接
解题思路
我们需要借助队列来实现，当root不为null时，那么我们将root入队，再将它出队打印，出对的时候我们添加左子树，添加右子树，循环上述操作，直到独队列为空。
public void order(TreeNode root){
Queue<TreeNode> queue=new LinkedList<>();
if(root==null){
return;
}
queue.offer(root);
while (!queue.isEmpty()){
TreeNode cur=queue.poll();
System.out.println(cur.val+" ");
if(cur.left!=null){
queue.add(cur.left);
}
if (cur.right!=null){
queue.add(cur.right);
}
}
}
除了递归的方式，还可以用非递归的方式：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list=new ArrayList<>();
if(root==null){
return list;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size=queue.size();
List<Integer> l=new ArrayList<>();
while (size!=0){
TreeNode cur=queue.poll();
size--;
l.add(cur.val);
if(cur.left!=null){
queue.add(cur.left);
}
if (cur.right!=null){
queue.add(cur.right);
}
}
list.add(l);
}
return list;
}
3.总结
在这篇文章中，博主主要分享了比较容易的一些二叉树题目，我们发现在做二叉树的习题时，大多都有用到递归思想，因为二叉树的子树本身也是一棵二叉树，所以当同学们遇到关于二叉树的问题时，可以往递归方向思考。在下一篇文章中，将继续和大家分享二叉树中比较复杂的题目。
下期预告：二叉树经典习题（下）
