Leetcode刷题笔记#108. Convert Sorted Array to Binary Search Tree

【小白刷题笔记】Leetcode #108. Convert Sorted Array to Binary Search Tree
【题目】Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

【思路：找到median】
题目要求是要转化为balanced BST，而不是普通的BST。balanced BST要求左子树和右子树的depth相差不能超过1。也就是说，左子树和右子树各自node的数量要尽可能一样多。于是我们就自然想到了用median作为root。
Step1：找到median(array)，把这个值设为root。这时median左边array也是sorted array，我们称为array_left。median右边的sorted array称为array_right。
Step2：找到median(array_left)，把这个值设为root.left。
Step3：找到median(array_right)，把这个值设为root.right。
……
接下来的步骤不过是在重复Step1，这个模式就是"找到array的median设为该node的value"，不断调用自身进行recursion直到遍历了所有的元素。

======
大家好！我是一名转专业小白，目前正在刷题中。我的背景是教育心理学，今年fall马上就要就读CS专业了（为了隐私暂且隐去学校和location）。
我发表这个帖子有两个目的，一是帮助我自己整理思路，还有一个目的是和大家交流分享~我希望可以帮助到和我一样正在努力转专业的同学们，也希望可以和大家和平交流。
谢谢：）


补充内容 (2020-8-11 11:54):
T(n): O(n)，因为我们需要traverse每一个median，也就是几乎n的每一个值。这里为什么不是O(lgn)呢？因为O(lgn)是树的高度，而我们要做的远多于树高，树的每一层的node我们都需要遍历。

这题挺经典的，算法也很直观。 建议楼主同时附上代码

bestlemontea 发表于 2020-7-22 12:38
这题挺经典的，算法也很直观。 建议楼主同时附上代码

很好的建议！