2020-10-12 打卡題-樹的中序遍歷
給你一棵所有節(jié)點為非負值的二叉搜索樹传轰，請你計算樹中任意兩節(jié)點的差的絕對值的最小值括细。
示例：
輸入：
1
\
3
/
2輸出：
1解釋：
最小絕對差為 1碉咆，其中 2 和 1 的差的絕對值為 1（或者 2 和 3）扮叨。提示：
樹中至少有 2 個節(jié)點沉桌。來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
著作權(quán)歸領(lǐng)扣網(wǎng)絡所有藤树。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)浴滴，非商業(yè)轉(zhuǎn)載請注明出處。
- 分析：本題關(guān)鍵點是二叉搜索樹的中序遍歷為上升序列岁钓，只要求上升序列中相鄰節(jié)點的差值最小值即為本題答案升略。
- 題解：
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;
}
}
