二叉搜索书递归

难度简单

题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes

解题思路

中序遍历（栈模拟 & 递归）
不难发现，在朴素解法中，我们对树进行搜索的目的是为了获取一个「有序序列」，然后从「有序序列」中获取答案。
而二叉搜索树的中序遍历是有序的，因此我们可以直接对「二叉搜索树」进行中序遍历，保存遍历过程中的最小值即是答案。

作者：AC_OIer
链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/gong-shui-san-xie-yi-ti-san-jie-shu-de-s-7r17/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
int ans = Integer.MAX_VALUE;
TreeNode prev = null;
public int minDiffInBST(TreeNode root) {
    dfs(root);
    return ans;
}
void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    if (prev != null) {
        ans = Math.min(ans, Math.abs(prev.val - root.val));
    }
    prev = root;
    dfs(root.right);
}