LeetCode: Convert Sorted List to Binary Search Tree 解题报告

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Show Tags

SOLUTION 1:

这个方法比较暴力，每次遍历当前list,找到中间的节点，建立 root,分别使用递归建立左树以及右树，并将左右树挂在root之下。但这个算法会复杂度很高。

建立root次数为N，每次遍历最多N次，最坏为N平方（实际不会这么多）

 public TreeNode sortedListToBST1(ListNode head) {
         ListNode fast = head;
         ListNode slow = head;

         ListNode pre = head;

         if (head == null) {
             return null;
         }

         TreeNode root = null;
         if (head.next == null) {
             root = new TreeNode(head.val);
             root.left = null;
             root.right = null;
             return root;
         }

         // get the middle node.
         while (fast != null && fast.next != null) {
             fast = fast.next.next;

             // record the node before the SLOW.
             pre = slow;
             slow = slow.next;
         }

         // cut the list to two parts.
         pre.next = null;
         TreeNode left = sortedListToBST1(head);
         TreeNode right = sortedListToBST1(slow.next);

         root = new TreeNode(slow.val);
         root.left = left;
         root.right = right;

         return root;
     }

SOLUTION 2:

 这个解法使用一个参数来记录当前正在操作的List Node. DFS本身的效果是，从head直到尾部建树，并且将currNode移动到size+1处。

这样可以在1次iterator 我们的List后直接建立树。

这是一种Bottom-up的建树方法。如果我们使用C++，则可以将List Node的指针直接做为入参。我们这里使用了类似的方法，不过，

Java不能使用指针，所以我们自建一个自定义的类，里面只有一个ListNode，这样我们就能方便地修改入参了（好纠结啊，这时主页君就开始怀念起C的指针了）,

:)

C++版本可以参见张磊哥哥的解答喔：）

http://fisherlei.blogspot.com/2013/01/leetcode-convert-sorted-list-to-binary.html

 public TreeNode sortedListToBST(ListNode head) {
         if (head == null) {
             return null;
         }

         int size = ;
         ListNode cur = head;
         while (cur != null) {
             size++;
             cur = cur.next;
         }

         CurrNode curNode = new CurrNode(head);
         return sortedListToBSTHelp(curNode, size);
     }

     public class CurrNode {
         ListNode node;

         CurrNode(ListNode node) {
             this.node = node;
         }
     }

     // when the recursion is done, the curr node should point to the node
     // which is the next of the block.
     public TreeNode sortedListToBSTHelp(CurrNode curr, int size) {
         if (size <= ) {
             return null;
         }

         TreeNode left = sortedListToBSTHelp(curr, size/);

         // because we want to deal with the right block.
         TreeNode root = new TreeNode(curr.node.val);
         curr.node = curr.node.next;

         TreeNode right = sortedListToBSTHelp(curr, size -  - size/);

         root.left = left;
         root.right = right;

         return root;
     }

SOLUTION 3:

这个解法使用一个instance variable 来记录当前正在操作的List Node. DFS本身的效果是，从head直到尾部建树，并且将currNode移动到size+1处。

这样可以在1次iterator 我们的List后直接建立树。

这是一种Bottom-up的建树方法。如果我们使用C++，则可以将List Node直接做为入参来改变之而不需要使用实例变量。

问题是：我们如果可以的话，尽量不要使用实例变量，因为它是各个Method 共享的，所以这个方法存在风险。因为变量有可能被别的方法修改。

这个dfs的意思就是 对一个以head 起始的list, size为大小的list建一个树，一个bfs树
并且这个dfs有一个作用 会把指针移动到这个要建的树的下一个位置

这样 我们先建立左树，        TreeNode left = dfs(head, size / 2);
经过这一行 cur就移动到了中间
我们建立 一个根         TreeNode root = new TreeNode(curNode.val);

把cur移动到下一个     curNode = curNode.next;
再用递归建立右树      

构造我们想要的树 返回根结果

root.left = left;
root.right = right;

return root;

 /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) { val = x; next = null; }
  * }
  */
 /**
  * Definition for binary tree
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
 public class Solution {
     ListNode curNode = null;

     public TreeNode sortedListToBST(ListNode head) {
         if (head == null) {
             return null;
         }

         int size = ;
         ListNode cur = head;
         while (cur != null) {
             size++;
             cur = cur.next;
         }

         curNode = head;
         return dfs(head, size);
     }

     // Use the size to control.
     public TreeNode dfs(ListNode head, int size) {
         if (size <= ) {
             return null;
         }

         TreeNode left = dfs(head, size / );
         TreeNode root = new TreeNode(curNode.val);

         // move the current node to the next place.
         curNode = curNode.next;
         TreeNode right = dfs(curNode, size - size /  - );

         root.left = left;
         root.right = right;

         return root;
     }
 }