108.将有序数组转换为二叉搜索树

LeetCode LeetCode 树二叉树数组二叉搜索树分治

发布时间 : 2000-01-10 01:00

字数:804 阅读 :

评论:

108.将有序数组转换为二叉搜索树

108.将有序数组转换为二叉搜索树

108.1 题目

给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案。

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按严格递增顺序排列

108.2 题解

递归法

// 方法一：递归法
// 将有序数组转换为高度平衡的二叉搜索树
static TreeNode SortedArrayToBST1(int[] nums)
{
    // 调用递归函数构建二叉搜索树
    return Helper1(nums, 0, nums.Length - 1);
}

// 辅助递归函数
static TreeNode Helper1(int[] nums, int left, int right)
{
    // 当 left 大于 right 时，返回 null
    if (left > right) return null;

    // 选择中间元素作为根节点
    int mid = left + (right - left) / 2;
    TreeNode node = new TreeNode(nums[mid]);

    // 递归构建左子树
    node.left = Helper1(nums, left, mid - 1);

    // 递归构建右子树
    node.right = Helper1(nums, mid + 1, right);

    // 返回当前构建的节点
    return node;
}

108.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
        // 平衡 二叉搜索树。
        //
        // 示例 1：
        //
        // 输入：nums = [-10,-3,0,5,9]
        // 输出：[0,-3,9,-10,null,5]
        // 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
        //
        // 示例 2：
        //
        // 输入：nums = [1,3]
        // 输出：[3,1]
        // 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
        //
        // 提示：
        // 1 <= nums.length <= 104
        // -104 <= nums[i] <= 104
        // nums 按 严格递增 顺序排列

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { -10, -3, 0, 5, 9 };
        TreeNode result1_1 = SortedArrayToBST1(nums1);
        Console.WriteLine("示例1 方法1 输出：");
        PrintTree(result1_1);



        // 示例 2
        int[] nums2 = { 1, 3 };
        TreeNode result2_1 = SortedArrayToBST1(nums2);
        Console.WriteLine("示例2 方法1 输出：");
        PrintTree(result2_1);


        #endregion
    }

    #region 答案

    // TreeNode 类定义
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x)
        {
            val = x;
        }
    }

    // 方法一：递归法
    // 将有序数组转换为高度平衡的二叉搜索树
    static TreeNode SortedArrayToBST1(int[] nums)
    {
        // 调用递归函数构建二叉搜索树
        return Helper1(nums, 0, nums.Length - 1);
    }

    // 辅助递归函数
    static TreeNode Helper1(int[] nums, int left, int right)
    {
        // 当 left 大于 right 时，返回 null
        if (left > right) return null;

        // 选择中间元素作为根节点
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        // 递归构建左子树
        node.left = Helper1(nums, left, mid - 1);

        // 递归构建右子树
        node.right = Helper1(nums, mid + 1, right);

        // 返回当前构建的节点
        return node;
    }


    // 打印二叉树（层次遍历）
    static void PrintTree(TreeNode root)
    {
        if (root == null)
        {
            Console.WriteLine("null");
            return;
        }

        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            TreeNode current = queue.Dequeue();
            if (current == null)
            {
                Console.Write("null ");
                continue;
            }

            Console.Write(current.val + " ");
            queue.Enqueue(current.left);
            queue.Enqueue(current.right);
        }

        Console.WriteLine();
    }

    #endregion
}

108.4 运行结果

示例1 方法1 输出：
0 -10 5 null -3 null 9 null null null null 
示例2 方法1 输出：
1 null 3 null null

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com