package week02;

import java.util.LinkedList;

import java.util.List;

/**

* @创建人 luoxiang

* @创建时间 2019/6/13 14:32

* @描述 LeetCode : 783. 二叉搜索树结点最小距离 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/

* 五毒神掌 ： 练习上一周的习题

*/

public class MinimumDistanceBetweenBstNodes783 {

public static void main(String[] args) {

TreeNode node = new TreeNode(4);

node.left = new TreeNode(2);

node.right = new TreeNode(6);

node.left.left = new TreeNode(1);

node.left.right = new TreeNode(3);

System.out.println(new MinimumDistanceBetweenBstNodes783().minDiffInBST(node));

}

/**

* Method 1 : 中序遍历， 然后两两相减取最小值

* 时间复杂度 ： O(2*N) ; 中序遍历 + 循环

* 空间复杂度 ： O(N) ; list 集合

*/

public int minDiffInBST(TreeNode root) {

List<Integer> list = new LinkedList<>();

inOrder(root, list);

int min = Integer.MAX_VALUE;

for (int i = 1; i < list.size(); i++) {

min = Math.min(min, list.get(i) - list.get(i - 1));

}

return min;

}

private void inOrder(TreeNode root, List list) {

if (root == null) return;

inOrder(root.left, list);

list.add(root.val);

inOrder(root.right, list);

}

/**

* Method 2 : 递归的方法 ， 用全局变量记忆存储上一个节点

* 时间复杂度 ： O(N)

* 空间复杂度 ： O(1)

*/

int min = Integer.MAX_VALUE;

TreeNode pre = null;

public int minDiffInBST2(TreeNode root) {

dfs(root);

return min;

}

private void dfs(TreeNode root) {

if (root == null) return;

dfs(root.left);

if (pre != null) min = Math.min(min, root.val - pre.val);

pre = root;

dfs(root.right);

}

}