给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
【思路】
题目要求在二叉搜索树上任意两节点的差的绝对值的最小值。
注意是二叉搜索树，二叉搜索树是有序的。遇到在二叉搜索树上求最值、差值之类的，就把它想成在一个有序数组上求最值、差值，这样就简答多了。
class Solution { TreeNode pre;// 记录上一个遍历的结点 int result = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { if(root==null)return 0; traversal(root); return result; } public void traversal(TreeNode root){ if(root==null)return; //左 traversal(root.left); //中 if(pre!=null){ result = Math.min(result,root.val-pre.val); } pre = root; //右 traversal(root.right); } }
class Solution { public int getMinimumDifference(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; int result = Integer.MAX_VALUE; if(root != null) stack.add(root); while(!stack.isEmpty()){ TreeNode curr = stack.peek(); if(curr != null){ stack.pop(); if(curr.right != null) stack.add(curr.right); stack.add(curr); stack.add(null); if(curr.left != null) stack.add(curr.left); }else{ stack.pop(); TreeNode temp = stack.pop(); if(pre != null) result = Math.min(result, temp.val - pre.val); pre = temp; } } return result; } }
