力扣530. 二叉搜索树的最小绝对差

思路1：中序遍历，递归排序成有序数组；因为是有序，只需要求相邻两个值的最小差值。

class Solution {
    ArrayList <Integer> list = new ArrayList();
    int ans = 100001;//题目最大 100000
    public int getMinimumDifference(TreeNode root) {
        getMinimumDifference1(root);
        //遍历计算排序好的两个最小绝对值。
        for(int i=list.size()-1;i>0;i--) {
           ans = Math.min(ans, list.get(i) - list.get(i-1));
        }
        return ans;
    }

//中序遍历，递归排序成有序数组
    public void getMinimumDifference1(TreeNode root) {
        if(root == null) return;
        getMinimumDifference1(root.left);
        list.add(root.val);
        getMinimumDifference1(root.right);
    }

    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路2：双指针法：中序遍历是有序的，在遍历的时候顺便相减，可以像有序数组的特性一样，一直相减，记录两个差值的最小绝对值。能少开一个数组的空间

class Solution {
    int ans = 100001;
    TreeNode preNode = null; //前一个节点
    public int getMinimumDifference(TreeNode root) {
        getMinimumDifference1(root);
        return ans;
    }

    //curNode 当前节点
    public void getMinimumDifference1(TreeNode curNode) {
        if(curNode == null) return;
        //左
        getMinimumDifference1(curNode.left);
        
        //中
        if(preNode != null) {
            ans = Math.min(ans, curNode.val - preNode.val);
        }
        //让preNode  一直跟在 curNode 后一个身位
        preNode = curNode;
        
        //右
        getMinimumDifference1(curNode.right);
    }
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28