Update 109.Convert-Sorted-List-to-Binary-Search-Tree.md

daydaygo · daydaygo · commit c4ccceaefaee · 2020-11-16T22:44:23.000+08:00
diff --git a/problems/109.Convert-Sorted-List-to-Binary-Search-Tree.md b/problems/109.Convert-Sorted-List-to-Binary-Search-Tree.md
@@ -1,4 +1,4 @@
-# 题目地址(109. 有序链表转换二叉搜索树)
+## 题目地址(109. 有序链表转换二叉搜索树)
 
 https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
 
@@ -21,78 +21,85 @@ https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
    /   /
  -10  5
 ```
+
 ## 前置知识
 - 递归
 - 二叉搜索树
-> 对于树中任意一个点，当前节点的值必然大于所有左子树节点的值     
+> 对于树中任意一个点，当前节点的值必然大于所有左子树节点的值
 同理,当前节点的值必然小于所有右子树节点的值
 
-
 ## 思路
 1. 获取当前链表的中点
 2. 以链表中点为根
 3. 中点左边的值都小于它,可以构造左子树,
 4. 同理构造右子树
 5. 循环第一步
 
-
 ### 双指针法
-  1. 定义一个快指针每步前进两个节点，一个慢指针每步前进一个节点
-  2. 当快指针到达尾部的时候，正好慢指针所到的点为中点
-  js Code
-  ```js
-      var sortedListToBST = function(head) {
-            if(!head) return null;
-            return run(head, null);
-      };
-
-      function run(head, tail){
-            if(head == tail) return null;
-            let fast = head;
-            let slow = head;
-            while(fast != tail && fast.next != tail){
-              fast = fast.next.next;
-              slow = slow.next;
-            }
-            let root = new TreeNode(slow.val);
-            root.left = run(head, slow);
-            root.right = run(slow.next, tail);
-            return root;
-      }
-  ```
-  
-  java Code:
-  ```java
-  class Solution {
-    public TreeNode sortedListToBST(ListNode head) {
-        if(head == null) return null;
-        return run(head,null);
-    }
-    private TreeNode run(ListNode head, ListNode tail){
-        if(head == tail) return null;
-        ListNode fast = head, slow = head;
-        while(fast != tail && fast.next != tail){
-            fast = fast.next.next;
-            slow = slow.next;
-        }
-        TreeNode root = new TreeNode(slow.val);
-        root.left = run(head, slow);
-        root.right = run(slow.next, tail);
-        return root;
-    }
-  }
-  ```
-  
-  **复杂度分析**
+1. 定义一个快指针每步前进两个节点，一个慢指针每步前进一个节点
+2. 当快指针到达尾部的时候，正好慢指针所到的点为中点
+
+- 语言支持: JS, Java
+
+JS Code:
+
+```js
+   var sortedListToBST = function(head) {
+         if(!head) return null;
+         return run(head, null);
+   };
+
+   function run(head, tail){
+         if(head == tail) return null;
+         let fast = head;
+         let slow = head;
+         while(fast != tail && fast.next != tail){
+           fast = fast.next.next;
+           slow = slow.next;
+         }
+         let root = new TreeNode(slow.val);
+         root.left = run(head, slow);
+         root.right = run(slow.next, tail);
+         return root;
+   }
+```
+
+Java Code:
+
+```java
+class Solution {
+ public TreeNode sortedListToBST(ListNode head) {
+     if(head == null) return null;
+     return run(head,null);
+ }
+ private TreeNode run(ListNode head, ListNode tail){
+     if(head == tail) return null;
+     ListNode fast = head, slow = head;
+     while(fast != tail && fast.next != tail){
+         fast = fast.next.next;
+         slow = slow.next;
+     }
+     TreeNode root = new TreeNode(slow.val);
+     root.left = run(head, slow);
+     root.right = run(slow.next, tail);
+     return root;
+ }
+}
+```
+
+**复杂度分析**
 - 时间复杂度：节点最多只遍历N*logN遍，时间复杂度为$O(NlogN)$
 - 空间复杂度：空间复杂度为$O(1)$
   
-### 缓存法 
+### 缓存法
 因为链表访问中点的时间复杂度为O(n),所以可以使用数组将链表的值存储,以空间换时间
 
-**代码**
+### 代码
+
+- 代码支持: JS, Go, PHP
 
 JS Code:
+
 ```js
 var sortedListToBST = function(head) {
     let res = []
@@ -114,6 +121,7 @@ function run(res){
 ```
 
 Go Code:
+
 ```go
 /**
  * Definition for singly-linked list.
@@ -152,6 +160,7 @@ func BST109(a []int) *TreeNode {
 ```
 
 PHP Code:
+
 ```php
 /**
  * Definition for a singly-linked list.
