wex5做网站,cp网站开发搭建,杭州专业网站设计策划,电商网站建设实施方案1. 题目
给定一个单链表#xff0c;其中的元素按升序排序#xff0c;将其转换为高度平衡的二叉搜索树。
本题中#xff0c;一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
来源#xff1a;力扣#xff08;LeetCode#xff09; 链…1. 题目
给定一个单链表其中的元素按升序排序将其转换为高度平衡的二叉搜索树。
本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
来源力扣LeetCode 链接https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
类似题目 LeetCode 108. 将有序数组转换为二叉搜索树
2. 解题
类似的方法快慢指针找到链表中点作为树的 root在中点前断开链表递归进行递归终止条件 head 为空返回 NULL如果只有一个节点了head slow直接返回head处的值建立的 root class Solution {
public:TreeNode* sortedListToBST(ListNode* head) {if(!head) return NULL;ListNode *slow, *slow_pre, *fast;slow fast head;slow_pre NULL;while(fast fast-next) {slow_pre slow;slow slow-next;fast fast-next-next;}if(slow_pre)slow_pre-next NULL;//断开链表if(slow slow ! head){TreeNode *root new TreeNode(slow-val);root-left sortedListToBST(head);root-right sortedListToBST(slow-next);return root;}return new TreeNode(head-val);}
};
