2020-10-12 打卡題-樹的中序遍歷

給你一棵所有節(jié)點(diǎn)為非負(fù)值的二叉搜索樹，請(qǐng)你計(jì)算樹中任意兩節(jié)點(diǎn)的差的絕對(duì)值的最小值。

示例：
輸入：
1
\
3
/
2

輸出：
1

解釋：
最小絕對(duì)差為 1，其中 2 和 1 的差的絕對(duì)值為 1（或者 2 和 3）。

提示：
樹中至少有 2 個(gè)節(jié)點(diǎn)。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

• 分析：本題關(guān)鍵點(diǎn)是二叉搜索樹的中序遍歷為上升序列，只要求上升序列中相鄰節(jié)點(diǎn)的差值最小值即為本題答案。
• 題解：

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;
        // 迭代方式進(jìn)行中序遍歷
        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;
    }
}