Leetcode783.二叉搜索树节点最小距离

1.题目

给定一个二叉搜索树的根结点 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的差值。

2.解答

1.使用数组

在使用dfs进行中序遍历的过程中,将节点一次存放到数组中,因为是二叉搜索树,所以此时数组一定是有序的,那么进行遍历取出其中的最小差值即可

由于题干比较短,刚开始审题时候看了一眼就开始寻找怎么找出递归条件了,后来再一看原来是他喵的二叉搜索树,忽略了一个相当重要的条件,所以以后做题时候要把题读明白再动手

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list;
    public int minDiffInBST(TreeNode root) {
        list = new ArrayList<>();
        dfs(root);
        int ans = Integer.MAX_VALUE;
        for(int i = 0;i < list.size()-1;i++){
            if(list.get(i+1) - list.get(i) < ans){
                ans = list.get(i+1) - list.get(i);
            }
        }
        return ans;
    }
    private void dfs(TreeNode node){
        if(node == null)    return;

        dfs(node.left);
        list.add(node.val);
        dfs(node.right);
    }
}

2.直接比较

另外一种方法可以在中序遍历的过程中直接维护更新值,不需要额外的数组空间

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //因为Java栈里面后面的栈帧需要使用到之前栈帧里面的pre,
    //所以将其定义在堆里面进行共享
    private TreeNode pre = null;
    private Integer ans = Integer.MAX_VALUE;
    public int minDiffInBST(TreeNode root) {
        dfs(root);
        return ans;
    }
    private void dfs(TreeNode node){
        if(node == null)    return;
        dfs(node.left);
        if(pre != null){
            ans = Math.min(ans,node.val-pre.val);
        }
        pre = node;
        dfs(node.right);
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode783二叉搜索树节点最小距离md