目录
题外话
本来昨天就想写完这篇文章,怎么样是不是很大胆?
一天写完三篇文章,所有人都很震惊!
但是因为个人感情原因,昨晚实在没心思写,包括我现在也是想东想西
但是这并不影响我更好的写下这篇文章
正题
今天依然是完成二叉树练习题,二叉树这块练习题也蛮多的,但是就是对二叉树性质和递归熟练掌握,没有别的
第一题
给定一个二叉树，判断它是否是平衡二叉树(所有结点子树高度差小于1)
第一题思路
先思考,想判断一棵二叉树是不是平衡二叉树,需要哪些操作
1.获取所有结点左右子树高度
2.获取所有结点左右子树高度的同时,求高度相减绝对值
第一题代码详解
//判断一棵二叉树是不是平衡二叉树
public boolean isBalanced(TreeNode root) {
//树没有结点,当做平衡二叉树
if (root==null)
{
return true;
}
//最后返回获取二叉树高度中是否满足平衡二叉树即可,不满足一定等于-1
return getHeight(root)!=-1;
}
//获取所有结点子树高度,并计算所有结点左右子树高度差
public int getHeight(TreeNode root)
{
//结点为空,返回0
if (root==null) {
return 0;
}
//将左右子树递归,并创建整型变量接收
int left=getHeight(root.left);
int right=getHeight(root.right);
//判断左子树右子树大于等于0的同时,计算左右子树高度差绝对值是否满足平衡二叉树条件
if(left>=0&&right>=0&&Math.abs(left-right)<=1)
{
//满足则返回二叉树高度
return left>right?left+1:right+1;
}
else{
//不满足返回-1
return -1;
}
}
第二题
给你一个二叉树的根节点root ， 检查它是否轴对称。
第二题思路
我们需要注意几个问题
1.根的左子树和根右子树相等
2.根结点的左子树的左子树和根节点的右子树的右子树相等
3.根节点的左子树的右子树和根节点的右子树的左子树相等
4.左子树为空,右子树不为空时,左子树不为空,右子树为空时
第二题代码详解
public boolean isSymmetric(TreeNode root) {
if (root==null)
{
return true;
}
//直接返回根的左子树和根的右子树的对称性判断结果即可
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree)
{
//首先判断左子树不为空,右子树为空和左子树为空,右子树不为空,这些都不是对称,返回false
if (leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null)
{
return false;
}
//当左子树和右子树都为空时是对称的,返回true
if (leftTree==null&&rightTree==null)
{
return true;
}
//当左子树和右子树的val值不一样,直接返回false
if (leftTree.val!=rightTree.val)
{
return false;
}
//最后再判断左子树的左子树和右子树的右子树是否相等,左子树的右子树和右子树的左子树是否相等即可
return isSymmetricChild(leftTree.left,rightTree.right)&& isSymmetricChild(leftTree.right,rightTree.left);
}
第三题
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
第三题思路
首先,我们只有一个先序遍历的字符串,我们需要几个操作
1.把字符串输入,
2.先把字符串中的每个字符放入字符型变量中
3.把字符变量按照先序顺序构造二叉树
4.中序遍历打印二叉树
第三题代码及详解
public class Main {
//创建一个静态变量i
public static int i=0;
public static void main(String[] args) {
//输入字符串
Scanner in=new Scanner(System.in);
while (in.hasNextLine())
{
//将先序遍历的字符串放入str
String str=in.nextLine();
//将字符串以先序遍历创建二叉树
TreeNode root=createTree(str);
//让二叉树中序遍历输出
inorder(root);
}
}
public static TreeNode createTree(String str){
//创建一个根root;
TreeNode root=null;
//将字符串从0开始转换成字符型,如果不是'#'就传给root,i自加1,然后递归,字符依次放入左子树,和右子树
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);
}
}
第四题
给你二叉树的根节点root ，返回其节点值的层序遍历 。 （即逐层地，从左到右访问所有节点）
第四题思路
这道题是将根结点,根的左子树,根的右子树先依次放入队列中,借助队列先进先出原则,从而实现层序遍历
遍历的同时把结点一层一层的放入List<List<Interage>>中
List<List<Interage>>相当于一个二维数组,之前杨辉大三角那篇讲过
第四题代码及详解
public List<List<Integer>> levelOrder(TreeNode root) {
//先建立相当于二维数组的ret
List<List<Integer>> ret=new ArrayList<>();
if (root==null)
{
return ret;
}
//建立队列q
Queue<TreeNode> q=new LinkedList<>();
//先将根结点放入q
q.offer(root);
//当q不为空
while (!q.isEmpty())
{
//建立相当于一维数组的tmp
List<Integer> tmp=new ArrayList<>();
//获取q中元素数量
int size=q.size();
//创建cur变量进行保存出列元素和获取出列元素左右子树
TreeNode cur=null;
//当元素数量不等于0
if (size!=0)
{
//把出列元素放入cur
cur=q.poll();
//出列元素值放入tmp,以便放入ret中
tmp.add(cur.val);
//队列元素减1
size--;
}
//打印出列元素值
System.out.print(cur.val+" ");
//如果出列元素左子树不为空,就把出列元素的左子树放入q中
if (cur.left!=null)
{
q.offer(cur.left);
}
//如果出列元素右子树不为空,就把出列元素的右子树元素放入q中
if (cur.right!=null)
{
q.offer(cur.right);
}
//每层结束执行需要把当前层出列的元素tmp放入ret
ret.add(tmp);
}
//循环结束,每层元素值都保存在ret中,返回ret
return ret;
}
第五题
判断一个树是不是完全二叉树(层序遍历)
第五题思路
这道题和第四题都差不多,利用队列先进先出原则,
完全二叉树用队列层序遍历每个元素之间不可能有空值,
换句话说两个元素之间有空值就说明不是完全二叉树,如果null出列开始后又有元素出列,则说明不是完全二叉树
第五题代码及详解
boolean isCompleteTree(TreeNode root)
{
//创建队列q
Queue<TreeNode> q=new LinkedList();
//将根节点放入q中
q.offer(root);
//如果q为空
while (!q.isEmpty())
{
//建立变量cur接收出列元素
TreeNode cur=q.poll();
//只要出列的元素不是null
if (cur!=null)
{
//就把cur的左子树右子树放入q中
q.offer(cur.left);
q.offer(cur.right);
}
//如果出列是null,则退出循环
else {
break;
}
}
//如果q不为空队列
while (!q.isEmpty())
{
//先查看对头元素,判断队头元素是不是null,如果是null则出列
TreeNode tmp=q.peek();
if (tmp==null)
{
q.poll();
}
//如果出列循环时遇到了不为null的元素则说明不是完全二叉树返回false
else {
return false;
}
}
//队列出完了,空了说明是完全二叉树,返回true
return true;
}
小结
今天状态确实不太好
送给大家一句话
如果真相带来痛苦,那么谎言只是雪上加霜.(泪目!!)
