[数据结构与算法]783.minimum-distance-between-bst-nodes

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

提示：

• 树中节点数目在范围 [2, 100] 内
• 0 <= Node.val <= 105
• 差值是一个正数，其数值等于两值之差的绝对值

解法

由于是bst,因此使用中序遍历,同时由于需要pre节点(因为差值最小,因此只会发生前后相连的节点,其他的情况是不会最小的),因此需要使用模拟栈的方式的进行中序遍历.

class Solution {
    public int minDiffInBST(TreeNode root) {


			int min = Integer.MAX_VALUE;
			
			Stack<TreeNode> stack = new Stack<>();
			
			TreeNode pre = null;
			while (null != root || ! stack.isEmpty()) {
				
				while (null != root) {
					stack.add(root);
					root = root.left;
				}
				
				TreeNode tmp = stack.pop();
				if(null == pre) {
					pre = tmp;
				}else {
					min = Math.min(min, tmp.val - pre.val);
               
					pre = tmp;
				}
				root = tmp.right;
			}

			return min;

		
    }
}