package question;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
 @author: Roderland
 @create: 2020年10月12日---13:27
*/
public class Question530 {
 public static void main(String[] args) {
 int[] arr = new int[]{1, 3, 2};
 TreeNode t1 = new TreeNode(1);
 TreeNode t2 = new TreeNode(3);
 TreeNode t3 = new TreeNode(2);
 t1.right = t2;
 t2.left = t3;
 System.out.println(new Question530().getMinimumDifference(t1));
 }
// List<Integer> list = new LinkedList<>();
//
// public int getMinimumDifference(TreeNode root) {
// dfs(root);
// list.sort(new Comparator<Integer>() {
// @Override
// public int compare(Integer o1, Integer o2) {
// return o1 - o2;
// }
// });
// int min = Integer.MAX_VALUE;
// for (int i = 0; i < list.size()-1; i++) {
// min=Math.min(min, list.get(i+1)-list.get(i));
// }
// return min;
// }

// public void dfs(TreeNode root) {
// if (root == null) return;
// list.add(root.val);
// dfs(root.left);
// dfs(root.right);
// }

 // 2
// int res;
// int pre;
//
// public int getMinimumDifference(TreeNode root) {
// pre = -1;
// res = Integer.MAX_VALUE;
// dfs2(root);
// return res;
// }
//
// public void dfs2(TreeNode root) {
// if (root == null) return;
// dfs2(root.left);
// if (pre != -1) res = Math.min(res, root.val - pre);
// pre = root.val;
// dfs2(root.right);
// }

 //3
// public int getMinimumDifference(TreeNode root) {
// int min = Integer.MAX_VALUE;
// int pre = -1;
// Deque<TreeNode> stack = new LinkedList<>();
// while (root!=null||!stack.isEmpty()) {
// while (root!=null) {
// stack.offerLast(root);
// root=root.left;
// }
// TreeNode node = stack.pollLast();
// if (pre!=-1) min=Math.min(min, node.val-pre);
// pre=node.val;
// root=node.right;
// }
// return min;
// }

 public int getMinimumDifference(TreeNode root) {
 TreeNode pre = null;
 int p=-1;
 int min = Integer.MAX_VALUE;
 while (root!=null) {
 if (root.left==null) {
 if (p!=-1) min=Math.min(min, root.val-p);
 p=root.val;
 root=root.right;
 } else {
 pre = root.left;
 while (pre.right!=null&&pre.right!=root) {
 pre = pre.right;
 }
 if (pre.right==null) {
 pre.right=root;
 root=root.left;
 } else {
 if (p!=-1) min=Math.min(min, root.val-p);
 p=root.val;
 pre.right=null;
 root=root.right;
 }
 }
 }
 return min;
 }
}