算法学习打卡第二十二天 链表
目录
一、题目
1、题目描述
2、基础框架
3、原题链接
二、解题报告
1、思路分析
2、代码详解
三、本题小知识
一、题目
1、题目描述
给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
示例 1:
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树。
示例 2:
输入: head = []输出: []
2、基础框架
Java 版本给出的基础框架代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } *//** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode sortedListToBST(ListNode head) { }}
提示:
head
中的节点数在[0, 2 * 104]
范围内-105 <= Node.val <= 105
3、原题链接
LeetCode 109. 有序链表转换二叉搜索树
二、解题报告
1、思路分析
根据平衡二叉树的定义,我们知道选取链表的中间结点为根节点可满足平衡二叉树
- 链表中间结点的查找:
- 定义快慢指针,初始都指向链表的最左边
- 让快指针每次移动两个结点,慢指针每次移动一个结点
- 当快指针指向尾结点或下一个结点为尾节点时(链表结点为奇数个或偶数个),慢指针指向中间节点
- 构造平衡二叉树:
- 将链表中间结点做为平衡二叉树的根节点
- 递归构造左右子树
2、代码详解
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } *//** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode sortedListToBST(ListNode head) {return constructTree(head,null); } //定义构建平衡二叉树的方法 public TreeNode constructTree(ListNode left,ListNode right) { //链表为空则直接返回 if(left==right){ return null; } ListNode mid=getMid(left,right); //创建树根节点 TreeNode rood = new TreeNode(mid.val); //递归构造左子树 rood.left=constructTree(left,mid); //递归构造右子树 rood.right=constructTree(mid.next,right); return rood; } //定义获取中间结点的方法 public ListNode getMid(ListNode left,ListNode right){ //定义快慢指针 ListNode slow=left; ListNode quick=left; //让快指针移动两次,慢指针移动一次,当快指针指向尾节点或下一个就是尾结点时,慢指针指向中间节点 while(quick!=right&&quick.next!=right){ quick=quick.next; quick=quick.next; slow=slow.next; } return slow; }}
三、本题小知识
链表,快慢指针运用
平衡二叉树(左右子树的高度相差不超过一)