南宁自己的网站,移动互联网技术学什么,商城类app定制开发,discuz轉wordpress根源简述 这道题是腾讯在2024/8/30考的一道面试题#xff0c;整体来说#xff0c;难度不大#xff0c;就是代码量稍稍有点儿大#xff0c;让我们一起来看一下吧 题目描述 整数无序双向链表能否转BST#xff08;二叉搜索树#xff09;#xff0c;如果能#xff0c;怎么转…根源简述 这道题是腾讯在2024/8/30考的一道面试题整体来说难度不大就是代码量稍稍有点儿大让我们一起来看一下吧 题目描述 整数无序双向链表能否转BST二叉搜索树如果能怎么转 (尽可能少的时间复杂度和空间复杂度)如果不能为什么 解题思路
这道题想都不用想一定是能转的要不然考你干啥接下来就看怎么转 我们可以把这个题拆成两个部分 1.整数无序双向链表进行排序
2.利用BST的性质中序遍历有序将排好序的双向链表再转为BST 这么一拆就清晰的多了就能逐个击破下面来让我们看一下代码是怎么实现的 代码实现
class ListNode {int val;ListNode prev;ListNode next;ListNode(int val) {this.val val;}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val val;}
}public class DoublyLinkedListToBST {// 将双向链表进行排序public ListNode sortDoublyLinkedList(ListNode head) {// 如果链表为空或只有一个节点直接返回if (head null || head.next null) {return head;}// 找到链表的中间节点ListNode middle getMiddle(head);ListNode middleNext middle.next;// 将链表从中间断开middle.next null;if (middleNext! null) {middleNext.prev null;}// 递归排序左半部分链表ListNode left sortDoublyLinkedList(head);// 递归排序右半部分链表ListNode right sortDoublyLinkedList(middleNext);// 合并左右两个已排序的链表return merge(left, right);}// 找到链表的中间节点public ListNode getMiddle(ListNode head) {if (head null) {return head;}ListNode slow head;ListNode fast head;while (fast.next! null fast.next.next! null) {fast fast.next.next;slow slow.next;}return slow;}// 合并两个已排序的链表public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyNode new ListNode(0);ListNode cur dummyNode;while (head1! null head2! null) {if (head1.val head2.val) {cur.next head1;head1.prev cur;head1 head1.next;} else {cur.next head2;head2.prev cur;head2 head2.next;}cur cur.next;}if (head1! null) {cur.next head1;head1.prev cur;}if (head2! null) {cur.next head2;head2.prev cur;}ListNode head dummyNode.next;head.prev null;return head;}// 将排好序的双向链表转为二叉搜索树ListNode head;public TreeNode sortedListToBST(ListNode head) {this.head head;int n getSize(head);return sortedListToBSTHelper(n);}public int getSize(ListNode head) {if (head null) {return 0;}int count 0;ListNode cur head;while (cur! null) {count;cur cur.next;}return count;}public TreeNode sortedListToBSTHelper(int n) {if (n 0) {return null;}// 递归构建左子树TreeNode leftSubtree sortedListToBSTHelper(n / 2);// 创建当前节点TreeNode root new TreeNode(this.head.val);// 连接左子树root.left leftSubtree;// 移动链表指针到下一个节点this.head this.head.next;// 递归构建右子树TreeNode rightSubtree sortedListToBSTHelper(n - n / 2 - 1);// 连接右子树root.right rightSubtree;return root;}
}
附言
如果上述代码看不懂的话建议先把这两道题刷一下148. 排序链表 - 力扣LeetCode109. 有序链表转换二叉搜索树 - 力扣LeetCode
