将整数列表转换为平衡二叉查找树,并以数组形式返回结果树 。
时间: 2023-04-05 22:04:50 浏览: 76
可以回答这个问题。以下是一个可能的解决方案:
首先,我们需要定义一个节点类,用于表示二叉树中的每个节点:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
然后,我们可以使用递归的方式将整数列表转换为平衡二叉查找树。具体来说,我们可以选择列表中间的元素作为根节点,然后递归地构建左子树和右子树,直到列表为空。为了保持平衡,我们可以选择左半部分的中间元素作为左子树的根节点,右半部分的中间元素作为右子树的根节点。
下面是实现代码:
```
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
```
最后,我们可以将树转换为数组形式返回。具体来说,我们可以使用中序遍历的方式将树中的元素按顺序添加到数组中。
下面是实现代码:
```
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
def treeToArray(self, root: TreeNode) -> List[int]:
if not root:
return []
return self.treeToArray(root.left) + [root.val] + self.treeToArray(root.right)
```
使用示例:
```
s = Solution()
nums = [1, 2, 3, 4, 5, 6, 7]
root = s.sortedArrayToBST(nums)
result = s.treeToArray(root)
print(result) # [1, 2, 3, 4, 5, 6, 7]
```