LeetCode算法题-Minimum Distance Bet

作者: 程序员小川 | 来源:发表于2019-04-23 08:47 被阅读14次

    这是悦乐书的第314次更新,第335篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第183题(顺位题号是783)。给定具有根节点值的二叉搜索树(BST),返回树中任何两个不同节点的值之间的最小差值。示例:

    给定的树[4,2,6,1,3,null,null]由下图表示:

          4
        /   \
      2      6
     / \    
    1   3  
    

    输出:1

    说明:请注意,root是TreeNode对象,而不是数组。该树中的任意节点最小差值为1,它发生在节点1和节点2之间,也发生在节点3和节点2之间。


    注意

    • BST的大小将在2到100之间。

    • BST始终有效,每个节点的值都是整数,每个节点的值都不同。

    本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

    02 第一种解法

    题目给的树是二叉树,并且是一个二叉搜索树,而其遵循左子树<根节点<右子树的大小关系,借助中序遍历,我们可以得到一组有序的节点值,从小到大排列。

    使用一个数组,将中序遍历的节点值依次添加进数组中去,然后遍历数组,比较前后两个节点之间的差值,最后得到最小差值并返回。中间遍历BST节点使用递归完成。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        private List<Integer> list = new ArrayList<Integer>();
    
        public int minDiffInBST(TreeNode root) {
            helper(root);
            int min = Integer.MAX_VALUE;
            for (int i=1; i<list.size(); i++) {
                int dif = Math.abs(list.get(i) - list.get(i-1));
                min = Math.min(dif, min);
            }
            return min;
        }
    
        public void helper(TreeNode root){
            if (root == null) {
                return ;
            }
            helper(root.left);
            list.add(root.val);
            helper(root.right);
        }
    
    }
    

    03 第二种解法

    针对第一种思路,我们也可以使用迭代的方法来解。使用栈来对BST进行遍历,依旧使用中序遍历,先找到BST中左子树里面的最底层左节点,然后再处理右节点。遍历完节点且将节点值添加进数组中后,对数组中的相邻元素求差值,依次比较得到最小差值返回即可。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        public int minDiffInBST(TreeNode root) {
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                if (!stack.isEmpty()) {
                    root = stack.pop();
                    list.add(root.val);
                    root = root.right;
                }
            }
            int min = Integer.MAX_VALUE;
            for (int i=1; i<list.size(); i++) {
                int dif = Math.abs(list.get(i) - list.get(i-1));
                min = Math.min(dif, min);
            }
            return min;
        }
    }
    

    04 第三种解法

    我们也可以不使用数组,使用一个变量来存储当前节点的前一个节点值即可,在处理当前节点时就可以直接计算两节点的差值,依旧使用中序遍历,此解法使用递归。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        private Integer prev = null;
        private int min = Integer.MAX_VALUE;
    
        public int minDiffInBST(TreeNode root) {
            helper(root);
            return min;
        }
    
        public void helper (TreeNode root) {
            if (root == null) {
                return ;
            }
            helper(root.left);
            if (prev != null) {
                min = Math.min(min, root.val-prev);
            } 
            prev = root.val;
            helper(root.right);
        }
    }
    

    05 第四种解法

    针对第三种解法,同样可以使用迭代的方式,依旧使用栈,和第二种解法里用栈的方式一样。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        public int minDiffInBST(TreeNode root) {
            Integer prev = null;
            int min = Integer.MAX_VALUE;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                if (!stack.isEmpty()) {
                    root = stack.pop();
                    if (prev != null) {
                        min = Math.min(min, root.val - prev);
                    }
                    prev = root.val;
                    root = root.right;
                }
            }
            return min;
        }
    }
    

    06 小结

    算法专题目前已日更超过五个月,算法题文章183+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode算法题-Minimum Distance Bet

        本文链接:https://www.haomeiwen.com/subject/ocrmgqtx.html