94 使用快慢指针把有序链表转换为二叉搜索树

2024-01-03 13:31:49

问题描述:给定一个单链表,其中的元素按升序排列,将其转换为高度平衡的二叉搜索树。在本题中,一个高度平衡二叉搜索树是指一个二叉树中每个节点的左右两个子树的高度差绝对值不超过1.

快慢指针解决:二叉搜索树的特点是当前节点大于左子树的所有节点,并且小于右子树的所有节点,并且每个节点都具有这个属性,题中说了是按照升序排列的链表,只需要找到链表的中间节点让其作为根节点,然后采用递归的方式进行,

public TreeNode changeListToSearch(ListNode first,ListNode end,TreeNode root)
{

if(first!=null&&end==null)
{
ListNode slow=first;
ListNode fast=first;
if(first->next==null)
{
TreeNode treeNodeRight=new TreeNode(slow.val);
if(root!=null)
{
root.right=treeNodeRight;
return treeNodeRight;
}
}else
{
while(fast!=null)
{
fast=fast.next.next;
slow=slow.next;
}
TreeNode treeNodeRight=new TreeNode(slow.val);
if(root!=null)
{
root.right=treeNodeRight;
}
changeListToSearch(first,slow,treeNodeRight);
changeListToSearch(slow->next,null,treeNodeRight);
return treeNodeRight;
}
???????

}
if(first!=null&&end!=null)
{
ListNode slow=first;
ListNode fast=first;
if(first.next==end)
{
TreeNode treeNodeLeft=new TreeNode(slow.val);
if(root!=null)
{
root.left=treeNodeLeft;
return treeNodeLeft;
}
}else
{
while(fast!=end)
{
fast=fast.next.next;
slow=slow.next;
}
TreeNode treeNodeLeft=new TreeNode(slow.val);
if(root!=null)
{
root.left=treeNodeLeft;
}
changeListToSearch(first,slow,treeNodeRight);
changeListToSearch(slow->next,null,treeNodeRight);
return treeNodeLeft;
}

}
}

public TreeNode ChangeListToSearch(ListNode listroot)
{
return ChangeListToSearch(listroot,null);

}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135358805
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。