这是悦乐书的第 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 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/b2fbb635beff