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

谁践踏了优雅 2022-05-09 10:20 194阅读 0赞

问题描述：

![70][]

算法思路：

注意到给定的数组是已经升序排列的，显然树的根节点为数组中点，那根节点的左子树和右子树又在数组什么位置呢？

假设数组中点的下标为mid，显然root.left在左半边：nums\[:mid\]中，同理root.right在右半边：nums\[mid+1:\]中。

由平衡的性质，不难想到root.left为左半边数组的中点，root.right为右半边数组的中点。这样递归地二分搜索下去，可以为每一个节点找到它的左右子树，即可完成树的构建。一般而言构建二叉树需要插入和平衡的操作，但如果我们事先就知道这棵树长什么样，完全可以用最省力的方法来一步到位。因为所有待插入的点都是已知的，就像建筑工人手里有了蓝图，我们可以自顶而下的按图索骥般一步步建构。

时间复杂度：O(n)

代码：

\# Definition for a binary tree node.  
\# class TreeNode(object):  
\#     def \_\_init\_\_(self, x):  
\#         self.val = x  
\#         self.left = None  
\#         self.right = None

class Solution(object):  
    def sortedArrayToBST(self, nums):  
        """  
        :type nums: List\[int\]  
        :rtype: TreeNode  
        """  
        if len(nums) == 0:  
            return None  
        mid = len(nums)//2  
        root = TreeNode(nums\[mid\])  
        left = nums\[:mid\]  
        right = nums\[mid+1:\]  
        root.left = self.sortedArrayToBST(left)  
        root.right = self.sortedArrayToBST(right)  
        return root

![70 1][]

[70]: /images/20220509/9c3c7daaa8534e7ea1fff838f5fbbbc9.png
[70 1]: /images/20220509/42e1ee0707a64492bfff2773aebd481e.png