algorithm001 · aiter · Apr 10, 2019 · Apr 16, 2019 · Apr 16, 2019 · Apr 17, 2019
diff --git a/Week_02/id_14/LeetCode_783_14.java b/Week_02/id_14/LeetCode_783_14.java
@@ -0,0 +1,163 @@
+/**
+ * https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
+ * <p>
+ * 783. 二叉搜索树结点最小距离
+ *
+ * <p> 简单
+ * <p> 树  binary tree
+ *
+ * @author aiter
+ * @date 2019/04/26 6:42 AM
+ */
+public class LeetCode_783_14 {
+    public static void main(String[] args) {
+        Solution solution = new Solution();
+
+        TreeNode root = new TreeNode(4);
+        root.left = new TreeNode(2);
+        root.left.left = new TreeNode(1);
+        root.left.right = new TreeNode(3);
+
+        root.right = new TreeNode(6);
+
+        int ret = solution.minDiffInBST(root);
+
+        System.out.println(String.format("预期值：1，实际值：%d", ret));
+
+        Solution2 solution2 = new Solution2();
+        System.out.println(String.format("预期值：1，实际值：%d", solution2.minDiffInBST(root)));
+    }
+
+    /**
+     * <pre>
+     *     要求：
+     *        任意两节点的差的最小值
+     *        <i>开始理解为父子节点的差值</i>
+     *     二叉搜索树：
+     *     1. 是有序的
+     *       2.1 中序遍历，就是一个有序的数列，再求相邻数组元素之间的最小差值
+     *       2.2 每个节点，查找他的中序遍历前序、后序节点，最小值只会出现在这里
+     *
+     *
+     *       2.1  结果，为什么？中序遍历O(n)+遍历求值O(n)。总：O(n)
+     *       执行用时 : 27 ms, 在Minimum Distance Between BST Nodes的Java提交中击败了5.25% 的用户
+     *       内存消耗 : 35.1 MB, 在Minimum Distance Between BST Nodes的Java提交中击败了55.36% 的用户
+     *       https://leetcode-cn.com/submissions/detail/17726878/
+     *
+     *       2.2
+     *       执行用时 : 1 ms, 在Minimum Distance Between BST Nodes的Java提交中击败了100.00% 的用户
+     *       内存消耗 : 34.6 MB, 在Minimum Distance Between BST Nodes的Java提交中击败了74.41% 的用户
+     * </pre>
+     */
+    static class Solution2 {
+        private final static int MAX = 100;
+
+        public int minDiffInBST(TreeNode root) {
+            if (root == null) {
+                return MAX;
+            }
+
+            int left = -1;
+            // 如果有左子树，那么最大值，一定是左子节点或左子树的最右节点
+            if (root.left != null) {
+                left = root.left.val;
+                TreeNode cur = root.left.right;
+                while (cur != null) {
+                    left = cur.val;
+                    cur = cur.right;
+                }
+            }
+
+            int min = MAX;
+            if (left > 0) {
+                min = Math.min(min, root.val - left);
+            }
+
+            int right = -1;
+            // 如果有右子树，那么最小值，一定是右子节点或右子树的最左节点
+            if (root.right != null) {
+                right = root.right.val;
+                TreeNode cur = root.right.left;
+                while (cur != null) {
+                    right = cur.val;
+                    cur = cur.left;
+                }
+            }
+            if (right > 0) {
+                min = Math.min(min, right - root.val);
+            }
+
+            //递归计算左子树、右子树的最小值k，在比较k与min的最小值
+            return Math.min(min, Math.min(minDiffInBST(root.left), minDiffInBST(root.right)));
+
+        }
+
+    }
+
+    static class Solution {
+        private final static int MAX = 100;
+
+        public int minDiffInBST(TreeNode root) {
+
+            DListNode inorderNode = new DListNode(root.val);
+
+            inorder(root, inorderNode);
+
+            DListNode cur = inorderNode;
+            System.out.println("-" + cur.val);
+            int min = MAX;
+            while (cur.pre != null) {
+
+                min = Math.min(min, Math.abs(cur.val - cur.pre.val));
+                cur = cur.pre;
+                System.out.println("pre-" + cur.val);
+            }
+            cur = inorderNode;
+            System.out.println("-" + cur.val);
+            while (cur.next != null) {
+
+                min = Math.min(min, Math.abs(cur.val - cur.next.val));
+                cur = cur.next;
+                System.out.println("next-" + cur.val);
+            }
+            return min;
+        }
+
+        private void inorder(TreeNode root, DListNode inorderNode) {
+            if (root == null) {
+                return;
+            }
+
+            if (root.left != null) {
+                DListNode pre = inorderNode.pre;
+                inorderNode.pre = new DListNode(root.left.val);
+                inorderNode.pre.next = inorderNode;
+                if (pre != null) {
+                    inorderNode.pre.pre = pre;
+                    pre.next = inorderNode.pre;
+                }
+                inorder(root.left, inorderNode.pre);
+            }
+            if (root.right != null) {
+                DListNode next = inorderNode.next;
+                inorderNode.next = new DListNode(root.right.val);
+                inorderNode.next.pre = inorderNode;
+                if (next != null) {
+                    inorderNode.next.next = next;
+                    next.pre = inorderNode.next;
+                }
+                inorder(root.right, inorderNode.next);
+            }
+        }
+    }
+
+    static class DListNode {
+        int val;
+        DListNode pre;
+        DListNode next;
+
+        DListNode(int x) {
+            val = x;
+        }
+    }
+}
diff --git a/Week_02/id_14/NOTE.md b/Week_02/id_14/NOTE.md
@@ -1 +1,54 @@
-# 学习笔记
+# 学习笔记
+> 本周重点：跳表、散列表、哈希算法、二叉树、红黑树
+
+本周主要还是练习，课程学习相对少一些。
+* 二叉树& 二叉搜索树
+  * binary tree 本身很基础，使用也是最多的一种。本身限定为二叉，0、1、2个子节点都符合要求，运用于实际时，可能是更多的限定，比如：i     * 完全能二叉树，那么只有1个子节点时，必须是左子字节。
+	 * leetcode上的求第二小的数字。限定子节点只能是0或2，不能是1
+  * 为了避免二叉树的高度太高，退化成链表，这样就基本失去了树的特征，这又引出了：
+	 * 平衡二叉树，左右子树的高度不能“相差太多”
+     * 完全二叉树，严格的平衡二叉树，左右高度相差最多为1。而且1个子节点时，必须是左子节点
+  	 * 满二叉树，一种特殊的完全二叉树。所有的非叶子节点数都是2
+     * 红黑树，比较难，后面再详细学习
+```
+      2               2           2           2
+     / \             / \         / \         / \
+    2   5           2   5       2    5      2    5
+       / \             / \     / \  /      / \  / \ 
+      5   7           5   7   5  7 6      5  7 6   7  
+     /
+    5
+    二叉树        平衡二叉树   完全二叉树    满二叉树
+```
+  > 都是二叉树，2、3、4都是平衡二叉树, 3、4都是完成二叉树。4是满二叉树
+  * 堆，就是一种完全二叉树。外加了一条，节点值大/小于左、右子节点值，分别就是大、小顶堆
+  * 二叉搜索树
+	* 本身是有序的，左子节点的值小于节点值，右子节点值大于节点值
+    * 基于上一条，中序遍历后，就是一个有序的序列
+    * leetcode上《783. 二叉搜索树结点最小距离》,就是典型的应用。开始笔者使用了中序遍历成一个有序的双向链表序列，再遍历链表，求相邻数值的最小差值，这样时间复杂度比较高(中序遍历O(n)+遍历链表求差值O(n)???)。后面利用二叉搜索树，任何节点的中序遍历前序节点要么是左子节点，要么是左子树的最右节点。后序节点同样的道理。最小距离肯定出现在当前节点与前序、后序节点的差值中。
+```
+            4             4
+          /  \          /  \
+         2    6        2    6
+       /  \            ^   / \
+      1    3           |  5   8
+           ^
+           |
+```
+  * 未完成：前、中、后序、层次遍历的实现
+* top k frequent words 
+  > 使用了hash表+双向链表的实现
+  * hash表，主要是O(1)时间复杂度定位对应的元素(也是双向链表中的节点)
+  * 把当前节点，从链中移除
+  * 再从链表头进行比较，选择插入的位置
+  * 最后从链表头，输出top K的
+* 利用队列实现广度优先搜索(BFS ，Breadth First Search)
+* 利用栈实现深度优先搜索(DFS ，Depth First Search)
+* 插入排序实现
+* 归并排序实现
+* 堆及堆排序
+上面几种实现本身没什么特别, 也是参考例子去实现的，有一点比较重要，以前都是学习理论，没有动手自己去实现。理解上还是不太深，自己实现一遍，加深了理解。比如：
+	* 广度优先，没实现前，记得当时的一个图，一层层去遍历，也记得有个队列。自己实现是走迷宫，实际实现就是从当前点，依次查看当前点的右、下、左、上是否可走，可走的话，就把右、下、左、上的点，加入队尾，然后从队头中取一个元素作为当前点，再重复这个过程。利用队列的先进先出(FIFO)，就实现了"层层推进"的效果。
+    * 而深度优先，则是采用栈的后进先出(LIFO)特性。实现了"一条路走到黑"的效果，只有真正没路可走了，而且还没走出迷宫，这时才能回到"岔路口"从另一条路再这样"一条路走到黑",每个岔路口，都是这样干的。这就是回溯（Backtrack)?
+
+> * 跳表：本周未涉及，周末有时间可以实现一下