网站seo教材,5ucms和wordpress的区别,长沙有哪些楼盘,网站上传的视频播放卡给定一个单链表的头节点 head #xff0c;其中的元素 按升序排序 #xff0c;将其转换为高度平衡的二叉搜索树。
本题中#xff0c;一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
思路一#xff1a;递归双指针
struct ListNode* getMedi…给定一个单链表的头节点 head 其中的元素 按升序排序 将其转换为高度平衡的二叉搜索树。
本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
思路一递归双指针
struct ListNode* getMedian(struct ListNode* left, struct ListNode* right) {struct ListNode* fast left;struct ListNode* slow left;while (fast ! right fast-next ! right) {fast fast-next;fast fast-next;slow slow-next;}return slow;
}struct TreeNode* buildTree(struct ListNode* left, struct ListNode* right) {if (left right) {return NULL;}struct ListNode* mid getMedian(left, right);struct TreeNode* root (struct TreeNode*)malloc(sizeof(struct TreeNode));root-val mid-val;root-left root-right NULL;root-left buildTree(left, mid);root-right buildTree(mid-next, right);return root;
}struct TreeNode* sortedListToBST(struct ListNode* head) {return buildTree(head, NULL);
}分析
本题给定一个链表的头节点求二叉搜索树与上题相同先找根节点再将左右子树通过递归的方式补充完整利用双指针的方法让快指针先到链表结尾再将中间的值赋给二叉树来创建二叉搜索树最后输出二叉树根节点
总结
本题考察二叉搜索树与链表的综合应用利用双指针找到根节点即可解决
