Day 16：108. Convert Sorted Array to Binary Search Tree

今日题目

题目连结：108. Convert Sorted Array to Binary Search Tree
题目主题：Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

今天的会开始进入 Binary Search Tree 的主题，这次题目是满重要的观念题，需要先了解 Binary Search Tree 的基本原则。

简单说说 Binary Search Tree

Binary Search Tree 是一颗有原则的树，原则如下：

1. 越小的数字在越左边的节点
2. 越大的数字在越右边的节点
3. 左边子节点一定小於父节点的值
4. 右边子节点一定大於父节点的值
5. 通常不会有节点出现重复的值

可以看看上图的范例，是一个符合Binary Search Tree 原则的树。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一个 nums 阵列，这个 nums 里面的值已经将顺序从小到大排好，本题的目标是将这个 nums 转成一颗 Binary Search Tree。另外这个 Binary Search Tree 要是一颗高度平衡的树，左边节点与右边节点深度不会超过一个。

约束：

• 1 <= nums.length <= 10的4次方
• -10的4次方 <= nums[i] <= 10的4次方
• nums 里面的值会从小到大排好

范例1

输入: nums = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解说: [0,-10,5,null,-3,null,9] 也是可以接受的答案，如上图所示，两种答案都可以是高平衡的Binary Search Tree。

范例2

输入: nums = [1,3]
输出: [3,1]
解说: [1,3]也是可以接受的答案，如上图所示，两种答案都可以是高平衡的 Binary Search Tree。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

此题目的解法，可以先有这样的想像，基本上一个排序好的阵列，要转成 Binary Search Tree 的感觉如下图:

可以看到其实概念就是把中间的值当根节点，左边跟右边在分别一个一个拉下来就可以形成一个高平衡的Binary Search Tree，下面的图解过程会有更清楚的图片说明。

文字描述

1. 写一个递回方法，传入要转Binary Search Tree的阵列、开始位置、结束位置、目前节点，最终回传完整的一颗TreeNode组成的树。
2. 此方法第一次呼叫会找到根节点，因为是高度平衡的Binary Search Tree，会用开始位置及结束位置找出中间的位置当根节点，公式为 (startIndex + endIndex) / 2。
3. 找到中间位置 nums[middleIndex] 就会当作目前的节点。
4. 第二次以後呼叫方法，会开始分别传入目前节点的左边节点及右边节点，用一样的方法找到节点的值，会一直递回到 nums 每个值都转到这棵树里面。

图解过程

范例：nums = [-15, -10, -3, 0, 5, 9, 13]

上图中，可以从 step1 开始看，每一回合我们都会有一个开始跟结束的位置，每次都会找到一个middle位置，而 step1 找到的就是我们的根节点。

step2 会在把 step1 的middle位置左边跟右边都分割下去，走一样的步骤，在分别在用开始跟结束位置找出middle位置，就会是根节点的两个子节点。

step3 再从 step2 分割下来，因为已经剩一个值了，因此开头结束及中间都会是同一个位置。最终形成下面的高平衡 Binary Search Tree。

这次的图解过程跟实际程序跑起来的顺序可能会有些差别，实际程序运作过程会比较类似Preorder的方式在找节点的值，会从左边的节点开始走完才会开始找右边的节点的值，只是在想像的过程个人觉得用上图的方式想像会比较顺。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def arrayToBST(self, nums, startIndex, endIndex, node:TreeNode = None):
        # 开始位置若大於结束位置，代表没有节点了
        if startIndex > endIndex:
            return node
        # 找到中间节点当目前节点
        middleIndex = int((startIndex + endIndex)/2)
        node = TreeNode(nums[middleIndex])
        # 找到目前节点的左子节点
        node.left = self.arrayToBST(nums, startIndex, middleIndex-1, node.left)
        # 找到目前节点的右子节点
        node.right = self.arrayToBST(nums, middleIndex+1, endIndex, node.right)
        
        return node
        
    
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.arrayToBST(nums, 0, len(nums)-1)

希望您今天能了解到...

1. Binary Search Tree 的基本观念
2. 108. Convert Sorted Array to Binary Search Tree 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：700. Search in a Binary Search Tree