力扣0109——有序链表转换二叉搜索树-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣0109——有序链表转换二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有序链表转换二叉搜索树

难度：中等

题目描述

给定一个单链表的头节点 head ，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

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

示例1：

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例2:

输入: head = []
输出: []

题解：

和 0108一样的思路，将链表中的元素转存到数组中，之后按照 0108 的思路解题即可文章来源地址https://www.toymoban.com/news/detail-834435.html

想法代码

using System;
using System.Collections;
using System.Collections.Generic;

public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val; 
        this.next = next;
    }
}

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this .val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        ListNode list = new ListNode
        {
            val = -10,
            next = new ListNode
            {
                val = -3,
                next = new ListNode
                {
                    val = 0,
                    next = new ListNode
                    {
                        val = 5,
                        next = new ListNode
                        {
                            val = 9
                        }
                    }
                }
            }
        };
        Solution solution = new Solution();
        TreeNode ans = solution.SortedListToBST(list);
        Console.ReadKey();
    }

    public TreeNode SortedListToBST(ListNode head)
    {
        Queue<int> queue = new Queue<int>();
        int index = 0;
        while (head != null)
        {
            queue.Enqueue(head.val);
            head = head.next;
        }
        int[] temp = new int[queue.Count];
        while (queue.Count > 0)
        {
            temp[index] = queue.Dequeue();
            index++;
        }

        return BackTrack(temp, 0, temp.Length - 1);
    }

    public TreeNode BackTrack(int[] nums, int start, int end)
    {
        if (start > end)
        {
            return null;
        }
        int mid = (start + end) / 2;
        return new TreeNode(nums[mid], BackTrack(nums, start, mid - 1), BackTrack(nums, mid + 1, end));
    }
}

到了这里，关于力扣0109——有序链表转换二叉搜索树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！