0. 链接
1. 题目
2. 思路1: 递归
- 中心点作为根节点, 左侧作为左子树, 右侧作为右子树
start = 0
end = len(nums) - 1
start + (end - start + 1) >> 1
- 特殊处理包含2个数和1个数的子树, 减少判断
3. 代码
# coding:utf8
from typing import List
# Definition for a binary tree node.
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:
def convert(nums, start, end):
if start < end - 1:
mid = start + ((end - start + 1) >> 1)
root = TreeNode(nums[mid])
root.left = convert(nums, start, mid - 1)
root.right = convert(nums, mid + 1, end)
return root
elif start == end - 1:
root = TreeNode(nums[end])
root.left = TreeNode(nums[start])
return root
elif start == end:
root = TreeNode(nums[end])
return root
else:
return None
return convert(nums, 0, len(nums) - 1)
def print_tree(root):
array = list()
def preorder_traverse(node):
array.append(node.val)
if node.left is not None:
preorder_traverse(node.left)
else:
array.append(None)
if node.right is not None:
preorder_traverse(node.right)
else:
array.append(None)
if root is not None:
preorder_traverse(root)
print(array)
solution = Solution()
print_tree(solution.sortedArrayToBST([-10, -3, 0, 5, 9]))
print_tree(solution.sortedArrayToBST([0, 1, 2, 3, 4, 5]))
输出结果
[0, -3, -10, None, None, None, 9, 5, None, None, None]
[3, 1, 0, None, None, 2, None, None, 5, 4, None, None, None]
网友评论