数据结构之二叉树由浅入深(四)

题外话

正题

第一题

第一题思路

第一题代码详解

第二题

第二题思路

第二题代码详解

第三题

第三题思路

第三题代码及详解

第四题

第四题思路

第四题代码及详解

第五题

第五题思路

第五题代码及详解

题外话

本来昨天就想写完这篇文章,怎么样是不是很大胆?

一天写完三篇文章,所有人都很震惊!

但是因为个人感情原因,昨晚实在没心思写,包括我现在也是想东想西

但是这并不影响我更好的写下这篇文章

正题

今天依然是完成二叉树练习题,二叉树这块练习题也蛮多的,但是就是对二叉树性质和递归熟练掌握,没有别的

第一题

给定一个二叉树，判断它是否是平衡二叉树(所有结点子树高度差小于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;
}