LeetCode 108 Convert Sorted Array to Binary Search Tree

栏目: 编程工具 · 发布时间: 6年前

内容简介：给予一个从小到大的数组, 构建一颗二叉平衡树, 即每个节点的两个子树的深度不能相差超过 1.例 :这道题有点类似于二分查找法, 即对二叉搜索树的反向推导, 每次取数组最中间的节点最为中节点, 左侧为左子树的内容, 右侧为右子树的内容, 直到不再存在子树.

给予一个从小到大的数组, 构建一颗二叉平衡树, 即每个节点的两个子树的深度不能相差超过 1.

例 :

给予数组: [-10, -3, 0, 5, 9]

返回以下树都是符合条件的: 
      0
     / \
   -3   9
   /   /
 -10  5


      0
    /  \
  -10   5
    \    \
    -3    9

解法

这道题有点类似于二分查找法, 即对二叉搜索树的反向推导, 每次取数组最中间的节点最为中节点, 左侧为左子树的内容, 右侧为右子树的内容, 直到不再存在子树.

import util.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, start, mid - 1);
        node.right = helper(nums, mid + 1, end);
        return node;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Sorted Array to Binary Search Tree. Memory Usage: 35.8 MB, less than 99.88% of Java online submissions for Convert Sorted Array to Binary

以上所述就是小编给大家介绍的《LeetCode 108 Convert Sorted Array to Binary Search Tree》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对码农网的支持！

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

图解物联网

［日］ NTT DATA集团、河村雅人、大塚纮史、小林佑辅、小山武士、宫崎智也、石黑佑树、小岛康平 / 丁　灵 / 人民邮电出版社 / 2017-4 / 59.00元

本书图例丰富，从设备、传感器及传输协议等构成IoT的技术要素讲起，逐步深入讲解如何灵活运用IoT。内容包括用于实现IoT的架构、传感器的种类及能从传感器获取的信息等，并介绍了传感设备原型设计必需的Arduino等平台及这些平台的选择方法，连接传感器的电路，传感器的数据分析，乃至IoT跟智能手机/可穿戴设备的联动等。此外，本书以作者们开发的IoT系统为例，讲述了硬件设置、无线通信及网络安全等运用Io......一起来看看《图解物联网》这本书的介绍吧!

码农工具

CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析

在线 JSON 格式化工具