有序链表转换二叉搜寻树
题目形容:给定一个单链表,其中的元素按升序排序,将其转换为高度均衡的二叉搜寻树。
本题中,一个高度均衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:递归
首先,将链表转化成数组,而后处理过程就和 LeetCode-108- 将有序数组转换为二叉搜寻树 的解法齐全一样了。
依据二叉搜寻树的性质,因为给定的数组是按升序排列的,所以能够确定数组 num 即为该二叉搜寻树的中序遍历序列,为了失去一颗均衡的二叉树,取数组两头地位的节点作为根节点,这样,左右子树的节点较为均衡,具体处理过程如下:
- 调用递归办法,初始的起始地位为数组的长度;
- 当终点地位大于起点地位时,阐明节点曾经遍历完了,间接返回空树;
- 获取两头地位的值作为根节点,这样左右子树的节点树是比拟平衡的;
- 而后递归取得以后根节点的左右子树;
- 最初返回根节点即为均衡的二叉搜寻树。
import com.kaesar.leetcode.ListNode;
import com.kaesar.leetcode.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
public class LeetCode_109 {public static TreeNode sortedListToBST(ListNode head) {Queue<Integer> queue = new LinkedList<>();
while (head != null) {queue.add(head.val);
head = head.next;
}
int[] nums = new int[queue.size()];
int index = 0;
// 先将链表转换成数组,即为二叉树的中序遍历序列
while (!queue.isEmpty()) {nums[index++] = queue.poll();}
// 调用递归办法,初始的起始地位为数组的长度
return sortedListToBST(nums, 0, nums.length - 1);
}
/**
* 递归
*
* @param nums
* @param left
* @param right
* @return
*/
private static TreeNode sortedListToBST(int[] nums, int left, int right) {
// 当终点地位大于起点地位时,阐明节点曾经遍历完了,间接返回空树
if (left > right) {return null;}
// 获取两头地位的值作为根节点,这样左右子树的节点树是较为平衡点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
// 而后递归取得以后根节点的左右子树
root.left = sortedListToBST(nums, left, mid - 1);
root.right = sortedListToBST(nums, mid + 1, right);
return root;
}
public static void main(String[] args) {ListNode head = new ListNode(-10);
head.next = new ListNode(-3);
head.next.next = new ListNode(-0);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(9);
sortedListToBST(head).print();}
}
【每日寄语】 任铁任金,定有可穿之砚;日磨日削,从无不锐之针。