编程题-有序链表转换二叉搜索树

ゞ浴缸里的玫瑰 2022-02-25 11:34 143阅读 0赞

[https://blog.csdn.net/qq\_38386316/article/details/83033169][https_blog.csdn.net_qq_38386316_article_details_83033169]

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1。

思路:中间的作为根节点进行构造,找链表的中间节点依旧可以使用快慢指针的方法进行找。

实例 :给定的有序链表： [-10, -3, 0, 5, 9],
    
    一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

参考 [https://blog.csdn.net/qq\_38386316/article/details/83033169][https_blog.csdn.net_qq_38386316_article_details_83033169] 包含main方法

<table> 
 <tbody> 
 <tr> 
 <td>&nbsp;public static ListNode stringToListNode(String input) { &nbsp; &nbsp; &nbsp; &nbsp; int[] nodes = stringToArrays(input); &nbsp; &nbsp; &nbsp; &nbsp; ListNode dummpy = new ListNode(-1); &nbsp; &nbsp; &nbsp; &nbsp; ListNode cur = dummpy; &nbsp; &nbsp; &nbsp; &nbsp; for(int x : nodes) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur.next = new ListNode(x); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cur = cur.next; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; return dummpy.next; &nbsp; &nbsp; } public static String treeNodeToString(TreeNode root) { &nbsp; &nbsp; &nbsp; &nbsp; if(root == null) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return "[]"; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; String ouput = ""; &nbsp; &nbsp; &nbsp; &nbsp; Queue&lt;TreeNode&gt; nodeQueue = new LinkedList&lt;&gt;(); &nbsp; &nbsp; &nbsp; &nbsp; nodeQueue.add(root); &nbsp; &nbsp; &nbsp; &nbsp; while(!nodeQueue.isEmpty()) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; TreeNode node = nodeQueue.remove(); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node == null) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ouput += "null, "; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ouput += String.valueOf(node.val) + ", "; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nodeQueue.add(node.left); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nodeQueue.add(node.right); &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; return "[" + ouput.substring(0, ouput.length() - 2) + "]"; &nbsp; &nbsp; } &nbsp;</td> 
 </tr> 
 </tbody> 
</table>

剑指offer36题  二叉搜索树和双向链表

思路: 在二叉搜索树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点的指针。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70][]![20190401212813876.png][]

改变原来指向左子节点和右子节点的指针，让他们分别指向前节点和后节点即可，**原先指向左子节点的指针调整为链表中指向前一个节点的指针  原先指向右子节点的指针调整为链表中指向后一个节点的指针**

按照中序递归遍历中，当我们遍历转换到根结点时，它的左子树已经转换成了一个排序的链表，并且此时链表尾部的值为左子树中最大结点。我们将它和根结点链接起来，此时根结点变成了链表尾部，接着去遍历右子树，我们知道中序遍历根结点后的一个结点此时为右子树最小结点，我们将它和根结点链接起来。左右子树再用这样的办法，即递归即可解决问题。

<table> 
 <tbody> 
 <tr> 
 <td> public static BinaryTreeNode baseconvert(BinaryTreeNode root, BinaryTreeNode lastNode) { if (root == null) return lastNode; BinaryTreeNode current = root; if (current.leftNode != null) lastNode=baseconvert(current.leftNode, lastNode); current.leftNode = lastNode; if (lastNode != null) lastNode.rightNode = current; lastNode = current; if (current.rightNode != null) lastNode=baseconvert(current.rightNode, lastNode); return lastNode; } 转自&nbsp;<a href="https://www.cnblogs.com/keedor/p/4467040.html" rel="nofollow">https://www.cnblogs.com/keedor/p/4467040.html</a> </td> 
 </tr> 
 </tbody> 
</table>

[https_blog.csdn.net_qq_38386316_article_details_83033169]: https://blog.csdn.net/qq_38386316/article/details/83033169
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190401210324712.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70
[20190401212813876.png]: /images/20220225/7a41b7826d3c468a9bf75f7b7560657d.png