Convert Sorted LinkedList(or Array) to BST

发表于

Convert Sorted Array to Binary Search Tree

Question

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis

这题需要将一个排好序的链表转成一个平衡二叉树，我们知道，对于一个二叉树来说，左子树一定小于根节点，而右子树大于根节点。所以我们需要找到链表的中间节点，这个就是根节点，链表的左半部分就是左子树，而右半部分则是右子树，我们继续递归处理相应的左右部分，就能够构造出对应的二叉树了。

故每次只需要找到数组的中间节点，在递归的对中点左右两部分的数组进行同样的convert操作赋给左右子树即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0)  return null;
        int start=0;
        int end=nums.length;
        return convert(nums,start,end);
    }
    
    private TreeNode convert(int[] nums,int start,int end){
        if(start==end)  return null;
        int mid=start+(end-start)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=convert(nums,start,mid);
        root.right=convert(nums,mid+1,end);
        return root;
    }
}

Convert Sorted List to Binary Search Tree

Question

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

Analysis

这题的难点在于如何找到链表的中间节点，我们可以通过fast，slow指针来解决，fast每次走两步，slow每次走一步，fast走到结尾，那么slow就是中间节点了。

Code

  1. Un-height-balanced
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
private ListNode p;
 private TreeNode root;
 public TreeNode sortedListToBST(ListNode head) {
     if(head==null)  return null;
     p=head;
     root=null;
     while(p!=null){
         int val=p.val;
         Insert(val);
         p=p.next;
     }
     return root;
 }
 
 private void Insert(int val){
     TreeNode tmp=this.root;
     if(root==null){
         root=new TreeNode(val);
     }else{
         while(true){
             if(tmp.val>val){            //Insert to left
                 if(tmp.left==null){
                     tmp.left=new TreeNode(val);
                     break;
                 }else{
                     tmp=tmp.left;
                 }
             }else{                      //Insert to right
                 if(tmp.right==null){
                     tmp.right=new TreeNode(val);
                     break;
                 }else{
                     tmp=tmp.right;
                 }
             }
         }
     }
 }
  1. Height- Balanced Ver
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null)  return null;
        return convert(head,null);
    }
    
    private TreeNode convert(ListNode start, ListNode end){
        if(start==end){
            return null;
        }
        ListNode slow=start;
        ListNode fast=start;
        while(fast!=end&&fast.next!=end){
            slow=slow.next;
            fast=fast.next.next;
        }
        
        TreeNode root=new TreeNode(slow.val);
        root.left=convert(start,slow);
        root.right=convert(slow.next,end);
        return root;
    }
}