[LintCode/LeetCode] Convert Sorted List to Balanced BST [二叉搜索树]
文章目录
Problem
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example
2
1->2->3 => / \
1 3
Note
用递归的方法来做,首先新建cur结点来复制head结点,然后计算链表head的长度,调用helper(start, end)函数建立平衡BST。
当链表为空时,helper()中出现start大于end,返回null。然后计算中点mid,以mid为界分别递归构建左右子树。顺序是,左子树-->根结点-->右子树。由于根节点root是直接取cur.val构建,当前的cur已经被取用。所以在下一次递归构建右子树之前,要让cur指向cur.next。最后将root和左右子树相连,返回root。
Solution
public class Solution {
ListNode cur;
public TreeNode sortedListToBST(ListNode head) {
cur = head;
int len = 0;
while (head != null) {
head = head.next;
len++;
}
return helper(0, len-1);
}
public TreeNode helper(int start, int end) {
if (start > end) return null;
int mid = start+(end-start)/2;
TreeNode left = helper(start, mid-1);
TreeNode root = new TreeNode(cur.val);
cur = cur.next;
TreeNode right = helper(mid+1, end);
root.left = left;
root.right = right;
return root;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论