初级算法-树

摘要

树的大部分问题都可以通过递归解决,即求一个树的某个值可以转化为求左子树/右子树的值

二叉树的最大深度

二叉树最大深度就是max(左子树的最大深度,右子树的最大深度) + 1(根节点)

public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left < right ? right + 1: left+1;
    }

验证二叉搜索树

二叉搜索树是自左向右的有序树,可以通过中序遍历,然后判断中序遍历的结果是否有序

public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        List<Integer> values = new ArrayList<Integer>();
        inOrder(root, values);
        for (int i = 0; i < values.size() - 1; i++) {
            if (values.get(i) >= values.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
     // 中序遍历
     public  void inOrder(TreeNode root, List<Integer> values) {
        if (root == null) {
            return;
        }
        inOrder(root.left, values);
        values.add(root.val);
        inOrder(root.right, values);
    }

对称二叉树

对称二叉树就是判断左右子树对称,递归方法即可

public boolean isSymmetric(TreeNode root) {
         if (root == null) {
            return true;
        }
        return isNodeSymmetric(root.right, root.left);
    }
    private boolean isNodeSymmetric(TreeNode right, TreeNode left) {
        if (right == null && left == null) {
            return true;
        }
        if (right == null || left == null) {
            return false;
        }
        boolean result = right.val == left.val && isNodeSymmetric(right.right, left.left) &&
                isNodeSymmetric(right.left, left.right);
        return result;
    }

二叉树的层次遍历

二叉树的层次遍历需要利用额外数据结构队列,将上一层的节点从左到右放在队列中,下一层的节点值,就是通过上一层的节点的左右节点得到。

public List<List<Integer>> levelOrder(TreeNode root) {
          if (root == null) {
            return Collections.emptyList();
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        LinkedList<TreeNode> nextQueue = new LinkedList<TreeNode>();
        queue.add(root);
        List<Integer> level0 = new ArrayList<Integer>();
        level0.add(root.val);
        result.add(level0);
        if (root.left != null) {
            nextQueue.add(root.left);
        }
        if (root.right != null) {
            nextQueue.add(root.right);
        }
        while (!nextQueue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            queue = (LinkedList<TreeNode>) nextQueue.clone();
            nextQueue.clear();
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    nextQueue.add(node.left);
                }
                if (node.right != null) {
                    nextQueue.add(node.right);
                }
            }
            if (!level.isEmpty()) {
                result.add(level);
            }
        }
        return result;
    }

上面这个解法有问题,queue其实没有用,还进行了队列的深拷贝,空间复杂度高,并且花费的时间比较久,

if (root == null) {
            return Collections.emptyList();
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> level0 = new ArrayList<Integer>();
        level0.add(root.val);
        result.add(level0);
        if (root.left != null) {
            queue.add(root.left);
        }
        if (root.right != null) {
            queue.add(root.right);
        }
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int count = queue.size();
            while (count-- > 0) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            if (!level.isEmpty()) {
                result.add(level);
            }
        }
        return result;

将有序数组转换为二叉搜索树

二叉搜索树本身就是有序的,所以将有序数组转换为二叉搜索树,就是按照左根右的顺序构建树,根节点就是中间的值,使用递归来解决

public TreeNode sortedArrayToBST(int[] nums) {
         if (nums == null || nums.length == 0) {
            return null;
        }
        return generateSortedArray(nums, 0, nums.length -1);
    }
      private TreeNode generateSortedArray(int[] nums , int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end)/2;
        TreeNode head = new TreeNode(nums[mid]);
        head.left = generateSortedArray(nums, start, mid -1);
        head.right = generateSortedArray(nums, mid+1,end);
        return head;
    
}

初级算法(2)-链表

初级算法-动态规划

本文分享自微信公众号 - 方丈的寺院(gh_c98f244e174d),作者:cnstonefang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 完整剖析SpringAOP的自调用

    spring全家桶帮助java web开发者节省了很多开发量,提升了效率。但是因为屏蔽了很多细节,导致很多开发者只知其然,不知其所以然,本文就是分析下使用spr...

    方丈的寺院
  • 数据库连接(2) - 为什么C3P0连接池那么慢

    在上一篇中我们介绍说客户端建立一次连接耗时太长(建立连接,设置字符集,autocommit等),如果在每个sql操作都需要经历建立连接,关闭连接。不仅应用程序响...

    方丈的寺院
  • 如何避免写出烂的业务代码(2)- DDD整改

    何避免写出烂的业务代码(1)一文中介绍过如何避免写出烂的业务代码,这边谈一谈领域驱动模型的实践

    方丈的寺院
  • python学习-4 python基础-

    补充:以上代码都是在pycharm里编写的。想要下载的朋友可以去百度首页搜索pycharm。

    py3study
  • isEmpty和isBlank的区别

    StringUtils方法的操作对象是java.lang.String类型的对象,是JDK提供的String类型操作方法的补充,并且是null安全的(即如果输入...

    微醺
  • C# excel文件导入导出

    在C#交流群里,看到很多小伙伴在excel数据导入导出到C#界面上存在疑惑,所以今天专门做了这个主题,希望大家有所收获!

    zls365
  • Python学习总结__Day1

    1、解释型:一边编译一边执行,劣势是运行速度慢,但通过运用PyPy交互解释器(JIT技术)会让python程序执行速度快很多。优势是可移植性强。

    py3study
  • C++写壳之高级篇

    之前在写了写壳基础篇,现在就来完成写壳高级篇。没有基础篇的知识,那理解高级篇就比较困难。有了写壳基础后,才能在其基础上逐步实现高级功能,加壳的目的主要是防止别人...

    战神伽罗
  • 【小家Spring】聊聊Spring中的那些【Metadata】,举例讲解:AnnotationMetadata、 MethodMetadata

    Metadata在org.springframework.core.type包名下,该包内类不多,主要有以下相关接口和类:

    YourBatman
  • 一次JDBC连接泄露问题的排查过程总结

    今天测试同学反馈在前端页面点击次数多了,就报500错误,数据显示不出来。于是我在后台服务日志中观察发现HikariCP连接池报如下的错误:

    九州暮云

扫码关注云+社区

领取腾讯云代金券