LintCode：1746 · 二叉搜索树结点最小距离

问题描述

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

• 二叉树的大小范围在 2 到 100。
• 二叉树总是有效的，每个节点的值都是整数，且不重复。

样例

输入: root = {4,2,6,1,3}
输出: 1
解释:
注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

          4
        /   \
      2      6
     / \    
    1   3  

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。

解题思路

A. 对二叉搜索树进行中序遍历可以获得一个递增序列;
B. 遍历这个序列，计算差值并找到最小的差值。

代码示例（JAVA）

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root:  a Binary Search Tree (BST) with the root node
     * @return: the minimum difference
     */

    public int minDiffInBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        tree2List(root, list);

        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < list.size() - 1; i++) {
            int diff = list.get(i + 1) - list.get(i);
            minDiff = Math.min(minDiff, diff);
        }

        return minDiff;
    }

    public void tree2List(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        tree2List(root.left, list);
        list.add(root.val);
        tree2List(root.right, list);
    }
}

借鉴了大佬的解法，可以把这个list优化掉：

public class Solution {
    /**
     * @param root:  a Binary Search Tree (BST) with the root node
     * @return: the minimum difference
     */
    Integer res = Integer.MAX_VALUE, pre = null;
    
    public int minDiffInBST(TreeNode root) {
        // Write your code here.
        if (root.left != null) {
            minDiffInBST(root.left);
        }
        if (pre != null) {
            res = Math.min(res, root.val - pre);
        }
        pre = root.val;
        if (root.right != null) {
            minDiffInBST(root.right);
        }
        return res;
    }
}