题目地址(108. 将有序数组转换为二叉搜索树)

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

题目描述

  1. 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
  3. 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
  7. 示例 1：
  9. 输入：nums = [-10,-3,0,5,9]
  10. 输出：[0,-3,9,-10,null,5]
  11. 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
  15. 示例 2：
  17. 输入：nums = [1,3]
  18. 输出：[3,1]
  19. 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
  24. 提示：
  26. 1 <= nums.length <= 104
  27. -104 <= nums[i] <= 104
  28. nums 按 严格递增 顺序排列

前置知识


公司

  • 暂无

思路

二叉树的构建问题很简单，说白了就是：构造根节点，然后构建左右子树。
一个有序数组对于 BST 来说就是中序遍历结果，根节点在数组中心，数组左侧是左子树元素，右侧是右子树元素。

分隔点的选择
分割点就是数组中间位置的节点。
如果数组长度为偶数，中间节点有两个，取哪一个？
取哪一个都可以，只不过构成了不同的平衡二叉搜索树。
例如：输入：[-10,-3,0,5,9]
如下两棵树，都是这个数组的平衡二叉搜索树：
image.png
如果要分割的数组长度为偶数的时候，中间元素为两个，是取左边元素 就是树1，取右边元素就是树2。
这也是题目中强调答案不是唯一的原因。 理解这一点，这道题目算是理解到位了

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public TreeNode sortedArrayToBST(int[] nums) {
  19.             return loop(nums , 0 , nums.length-1);
  20.         }
  22.         public TreeNode loop(int[] nums , int left,int right) {
  23.             //如果左界大于右界说明数组遍历完毕
  24.             if (left > right) {
  25.                 return null;
  26.             }
  27.             //找到中间节点 将他作为根节点
  28.             int mid = (left+right)/2;
  29.             TreeNode root = new TreeNode(nums[mid]);
  30.             //根节点的左边是将左边的有序数组继续构建成二叉搜索树 left为left-中间节点-1 right为中间节点+1-right
  31.             root.left = loop(nums, left, mid-1);
  32.             root.right = loop(nums, mid+1, right);
  33.             return root;
  34.         }
  35.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：108. 将有序数组转换为二叉搜索树 - 图2#card=math&code=O%28n%29&id=LwEjL)
  • 空间复杂度：108. 将有序数组转换为二叉搜索树 - 图3#card=math&code=O%28n%29&id=PYJra)