算法宝典2——Java版本(此系列持续更新,这篇文章目前3道)(有题目的跳转链接)(此份宝典包含了二叉树的算法题)

简介: 算法宝典2——Java版本(此系列持续更新,这篇文章目前3道)(有题目的跳转链接)(此份宝典包含了二叉树的算法题)

一、二叉树的算法题(目前3道)

1. 平衡二叉树(力扣)

题目:给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ,空树也是平衡二叉树。

思路:

代码:

// 获取二叉树的高度
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftCount = maxDepth(root.left);
        int rightCount = maxDepth(root.right);
        return (leftCount > rightCount) ? leftCount + 1 : rightCount + 1;
    }
    //判断是否为平衡二叉树
    public boolean isBalanced(TreeNode root) {
        //如果为空树,返回null
        if(root == null){
            return true;
        }
        //获取左右子树的高度
        int leftTreeHigh = maxDepth(root.left);
        int righTreeHigh = maxDepth(root.right);
        //isBalanced(root.left) && isBalanced(root.left)是判断左右子树是不是也满足平衡二叉树的定义
        return Math.abs(leftTreeHigh - righTreeHigh) < 2
                && isBalanced(root.left) && isBalanced(root.right);
    }

如果是按照上述代码的思路来写,此算法的时间复杂度就是O(n^2)!!!这是在是太大了!

什么原因造成的呢?

答:我们在求3结点的高度时,其实就把9结点的高度求出来了,但是递归到9结点的时候,又求了一次,导致重复求树的高度,有n个结点,每个结点就要求n次高度,也就是n*n!!!

所以我们可以把代码改一下:

public int maxDepth2(TreeNode root) {
        //空树,证明没有子树,他的高度就是0
        if(root == null){
            return 0;
        }
        int leftH = maxDepth2(root.left);//只要左子树的高度返回是-1,表示左子树不满足平衡二叉树的定义
        if(leftH < 0)
            return -1;
        int rightH = maxDepth2(root.right);//只要右子树的高度返回是-1,表示左子树不满足平衡二叉树的定义
        if (rightH < 0)
            return -1;
        if(Math.abs(leftH - rightH) <= 1){
            return Math.max(leftH,rightH) + 1;//满足定义,返回高度最高的子树,并+1
        }else{
            return -1;//不满足定义,返回-1
        }
    }
    public boolean isBalanced2(TreeNode root) {
        return maxDepth2(root) >= 0;
    }

运行结果:

2.  对称二叉树(力扣)

题目:给你一个二叉树的根节点 root , 检查它是否轴对称。

思路:

和这道判断两个二叉树是不是一样的题目类似:算法宝典1——Java版本(此系列持续更新,这篇文章有20道)(有题目的跳转链接)(此份宝典包含了链表、栈、队列、二叉树的算法题)_木子斤欠木同的博客-CSDN博客

让左子树的左结点和右子树的右子树相比较,然后递归下去,然后就可以判断是不是对称二叉树!!!

代码:

//判断对称树
    public boolean isSymmetricChild(TreeNode leftChild, TreeNode rightChild) {
        //这是路径的判断
        if (leftChild != null && rightChild == null || leftChild == null && rightChild != null) {
            return false;
        }
        if (leftChild == null && rightChild == null) {
            return true;
        }
        //这是值的判断
        if (leftChild.val != rightChild.val) {
            return false;
        }
        return isSymmetricChild(leftChild.left, rightChild.right)
                && isSymmetricChild(leftChild.right, rightChild.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

运行结果:

3. 二叉树的层序遍历(力扣)

题目:给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

思路:

代码:

//不带链表的形式
    public void levelOrder1(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode poll = queue.poll();
            System.out.println(poll.val+ " ");
            if(poll.left != null){
                queue.offer(poll.left);
            }
            if(poll.left != null){
                queue.offer(poll.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> list = new ArrayList<>();
            while(size != 0){//第二层循环表示当前层次的元素数量
                TreeNode cur = queue.poll();
                size--;
                list.add(cur.val);//将元素保存到列表
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            List.add(list);
        }
        return List;
    }

运行结果:

相关文章
|
12天前
|
存储 安全 Java
从入门到精通:Java Map全攻略,一篇文章就够了!
【10月更文挑战第17天】本文详细介绍了Java编程中Map的使用,涵盖Map的基本概念、创建、访问与修改、遍历方法、常用实现类(如HashMap、TreeMap、LinkedHashMap)及其特点,以及Map在多线程环境下的并发处理和性能优化技巧,适合初学者和进阶者学习。
30 3
|
4天前
|
Java Linux Windows
如何查看已安装的 Java 版本
要查看已安装的 Java 版本,打开命令提示符或终端,输入 `java -version`,回车后即可显示当前系统中 Java 的版本信息。
|
4天前
|
Ubuntu Java Linux
如何检查 Java 版本是否兼容
要检查Java版本是否兼容,可在命令行输入“java -version”查看当前安装的Java版本,然后对比目标应用所需的Java版本,确保其满足要求。
|
10天前
|
存储 安全 Java
从入门到精通:Java Map全攻略,一篇文章就够了!
【10月更文挑战第19天】本文介绍了Java编程中重要的数据结构——Map,通过问答形式讲解了Map的基本概念、创建、访问与修改、遍历方法、常用实现类(如HashMap、TreeMap、LinkedHashMap)及其特点,以及Map在多线程环境下的使用和性能优化技巧,适合初学者和进阶者学习。
35 4
|
25天前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
25 1
|
25天前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
22 1
|
27天前
|
Java Docker 容器
java版本学习网站又添加了一个libgdx模块
java版本学习网站之前添加了docker,想了想还是再把libgdx添加进去吧。
24 3
|
7天前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
11 0
|
17天前
|
人工智能 算法 JavaScript
无界SaaS与AI算力算法,链接裂变万企万商万物互联
本文介绍了一种基于无界SaaS与AI算力算法的商业模式的技术实现方案,涵盖前端、后端、数据库及AI算法等关键部分。通过React.js构建用户界面,Node.js与Express搭建后端服务,MongoDB存储数据,TensorFlow实现AI功能。提供了项目结构、代码示例及部署建议,强调了安全性、可扩展性和性能优化的重要性。
|
19天前
|
Java Maven Spring
查看springboot版本支持最高的java版本
截至最近更新,Spring Boot 3.0及以上版本支持的最高Java版本为Java 17。鉴于技术的不断演进,建议直接参考Spring Boot的官方文档获取最准确的支持信息,因为这些版本兼容性可能会随着新版本的发布而有所变化。选择与你的Spring Boot版本相匹配的Java版本,可以确保充分利用框架特性,同时保证项目的稳定性和前瞻性。
34 0