leetcode 108. Convert Sorted Array to Binary Search Tree
LeetCode to Array Tree search Binary sorted convert
2023-09-14 09:11:53 时间
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.
Example:
Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5
# 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 """ def build_bst(arr, i, j): if i > j: return None mid = (i+j)>>1 node = TreeNode(arr[mid]) node.left = build_bst(arr, i, mid-1) node.right = build_bst(arr, mid+1, j) return node return build_bst(nums, 0, len(nums)-1)
迭代解法,本质上是先序遍历:
# 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 not nums: return None q = [(0, len(nums)-1)] ans = TreeNode(0) nodes = [ans] while q: i, j = q.pop() mid = (i+j)>>1 node = nodes.pop() node.val = nums[mid] if mid+1 <= j: node.right = TreeNode(0) q.append((mid+1, j)) nodes.append(node.right) if mid-1 >= i: node.left = TreeNode(0) q.append((i, mid-1)) nodes.append(node.left) return ans
相关文章
- leetcode 191 二进制中1的个数 js 实现
- ☆打卡算法☆LeetCode 221. 最大正方形 算法解析
- leetcode-剑指offer59-I 滑动窗口的最大值
- LeetCode每日一题06-13
- LeetCode周赛298,阳光普照,参加就能简历免筛
- leetcode-88合并两个有序数组(双指针)
- leetcode 792_单词编码
- JavaScript刷LeetCode-字符串类解题技巧
- leetcode-142. 环形链表 II
- JavaScript刷LeetCode拿offer-经典高频40题
- leetcode #77 in cpp[通俗易懂]
- leetcode最长无重复字符串_直线是一维还是二维
- LeetCode周赛331,思维题训练场
- To add browser notifications to an online customer support live chat service system - gofly - self h
- Leetcode LRU 缓存机制
- LeetCode每日一题之817题链表组件
- 利用Oracle TO函数实现数据转换(oracle to_函数)