力扣入口 109.有序链表转化二叉搜索树
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
思路加图解
思路1:
class Solution {
//获取中间结点,左闭右开 方便表示head,null
public ListNode getMidNode(ListNode left, ListNode right){
ListNode fast = left;
ListNode slow = left;
while(fast != right && fast.next != right){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
//递归构建二叉搜索树 左闭右开 方便表示head,null
public TreeNode buildTree(ListNode left,ListNode right){
if(left == right){
return null;
}
//获取中间结点
ListNode mid = getMidNode(left,right);
//构建根结点
TreeNode root = new TreeNode(mid.val);
//构造左子树
root.left = buildTree(left,mid);
//构造右子树
root.right = buildTree(mid.next,right);
//返回根结点
return root;
}
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head,null);
}
}
思路2:
class Solution {
ListNode globalHead;
public TreeNode sortedListToBST(ListNode head) {
globalHead = head;
int length = getLength(head);
return buildTree(0, length - 1);
}
public int getLength(ListNode head) {
int ret = 0;
while (head != null) {
++ret;
head = head.next;
}
return ret;
}
//中序遍历,构造二叉树
//
public TreeNode buildTree(int left, int right) {
if (left > right) {
return null;
}
int mid = (left + right + 1) / 2;
TreeNode root = new TreeNode();
root.left = buildTree(left, mid - 1);
root.val = globalHead.val;
globalHead = globalHead.next;
root.right = buildTree(mid + 1, right);
return root;
}
}
最难不过坚持!