关于java:LeetCode109有序链表转换二叉搜索树

有序链表转换二叉搜寻树

题目形容：给定一个单链表，其中的元素按升序排序，将其转换为高度均衡的二叉搜寻树。

本题中，一个高度均衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归

首先，将链表转化成数组，而后处理过程就和 LeetCode-108-将有序数组转换为二叉搜寻树 的解法齐全一样了。

依据二叉搜寻树的性质，因为给定的数组是按升序排列的，所以能够确定数组num即为该二叉搜寻树的中序遍历序列，为了失去一颗均衡的二叉树，取数组两头地位的节点作为根节点，这样，左右子树的节点较为均衡，具体处理过程如下：

• 调用递归办法，初始的起始地位为数组的长度；
• 当终点地位大于起点地位时，阐明节点曾经遍历完了，间接返回空树；
• 获取两头地位的值作为根节点，这样左右子树的节点树是比拟平衡的；
• 而后递归取得以后根节点的左右子树；
• 最初返回根节点即为均衡的二叉搜寻树。

<code class="java">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();
    }
}

【每日寄语】 任铁任金，定有可穿之砚；日磨日削，从无不锐之针。

喜欢 (0)赏

[搞代码]

分享 (0)