【Lintcode】1033. Minimum Difference Between BST Nodes_综合

题目地址：

https://www.lintcode.com/problem/minimum-difference-between-bst-nodes/description

给定一棵二叉搜索树，求其两个节点差的绝对值的最小值。

直接中序遍历树即可，答案一定产生于中序遍历的某个节点与其前驱的差之中。代码如下：

import java.util.Deque;
import java.util.LinkedList;public class Solution {
    /*** @param root: the root* @return: the minimum difference between the values of any two different nodes in the tree*/public int minDiffInBST(TreeNode root) {
    // Write your code hereint res = Integer.MAX_VALUE;// last记录cur的前驱TreeNode cur = root, last = null;Deque<TreeNode> stack = new LinkedList<>();while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
    stack.push(cur);cur = cur.left;}cur = stack.pop();if (last != null) {
    res = Math.min(res, cur.val - last.val);}last = cur;cur = cur.right;}return res;}
}class TreeNode {
    int val;TreeNode left, right;public TreeNode(int val) {
    this.val = val;}
}

时间复杂度 $O (n)$ ，空间 $O (h)$ 。