给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。
示例：
输入: root = [4,2,6,1,3,null,null] 输出: 1 解释: 注意，root是树节点对象(TreeNode object)，而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:
4 / \ 2 6 / \ 1 3
最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
自己写的垃圾代码，每遍历一个结点就去遍历它的左右子树的最大值和最小值，然后相减取绝对值，保存一个相对较小的。
/** * 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) { //空树 if(root == null) return 0; //初始一个最大值 int min = 0x7fffffff; LinkedList<TreeNode> stack = new LinkedList<>(); stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); //将该结点的左子树最大值或者右子树最小值 的差值与当前结点的val相减，取绝对值 int presentLeft = node.left==null? 0x7ffffff:leftMax(node.left); int presentRight = node.right==null? 0x7ffffff:rightMin(node.right); int presentMin = Math.min(Math.abs(node.val - presentLeft),Math.abs(node.val - presentRight)); //更新最小值 min = Math.min(presentMin,min); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } return min; } //该结点左子树最大值 public int leftMax(TreeNode root){ while(root.right != null){ root = root.right; } return root.val; } //该结点右子树最小值 public int rightMin(TreeNode root){ while(root.left != null){ root = root.left; } return root.val; } }更优解：直接中序遍历得出序列数组，然后遍历这个有序数组即可
class Solution { public int minDiffInBST(TreeNode root){ ArrayList<Integer> list = new ArrayList<>(); inOrder(root,list); int min = Integer.MAX_VALUE; for (int i = 0; i < list.size() - 1; i++) { min = Math.min(list.get(i+1) - list.get(i),min); } return min; } public void inOrder(TreeNode root, ArrayList<Integer> list){ if(root == null) return; inOrder(root.left,list); list.add(root.val); inOrder(root.right,list); } }
