首页 > 代码库 > [LeetCode系列]有序链表转换为平衡BST的递归解法
[LeetCode系列]有序链表转换为平衡BST的递归解法
给定有序链表(元素由小到大), 试问如何将其转换为一个平衡BST?
平衡BST: 任意节点的左右子树的深度差值不大于1.
主要思想是用递归. Trick是使用快慢指针来获取中间节点. 获得中间节点后, 将其设为此次递归的root, 随后删除此节点, 并将前一节点的next置NULL. 随后, 对中间节点的前后部分分别进行递归调用, 并将返回值作为其左右子树.
代码如下:
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 /**10 * Definition for binary tree11 * struct TreeNode {12 * int val;13 * TreeNode *left;14 * TreeNode *right;15 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}16 * };17 */18 class Solution {19 public:20 TreeNode *sortedListToBST(ListNode *head) {21 if(head == NULL) return NULL;22 if(head->next == NULL) return new TreeNode(head->val);23 ListNode *step1 = head;24 ListNode *step2 = head->next;25 while(step2->next != NULL && step2->next->next != NULL){26 step1 = step1->next;27 step2 = step2->next->next;28 }29 TreeNode *root = new TreeNode(step1->next->val);30 ListNode *head2 = step1->next->next;31 delete step1->next;32 step1->next = NULL; // cut list into two parts33 root->left = sortedListToBST(head);34 root->right = sortedListToBST(head2);35 return root;36 }37 };
[LeetCode系列]有序链表转换为平衡BST的递归解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。