【Leetcode-530】树-二叉搜索树的最小绝对差

2020-10-12 打卡题-树的中序遍历

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：
输入：
1
\
3
/
2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：
树中至少有 2 个节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 分析：本题关键点是二叉搜索树的中序遍历为上升序列，只要求上升序列中相邻节点的差值最小值即为本题答案。
• 题解：

import java.util.ArrayList;
import java.util.Stack;

public class GetMinimumDifference {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    public int getMinimumDifference(TreeNode root) {
        int min_value = Integer.MAX_VALUE;
        int value_diff = 0;
        TreeNode p = root;
        // 迭代方式进行中序遍历
        while(p!=null || stack.size()>0){
            while(p!=null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            arrayList.add(p.val);
            p = p.right;
        }
        for (int i = 1; i < arrayList.size(); i++) {
            value_diff = arrayList.get(i)-arrayList.get(i-1);
            if(value_diff < min_value) min_value = value_diff;
        }
        return min_value;
    }
}