108. Convert Sorted Array to Binary Search Tree
Tags:
Easy
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach
Để chuyển một mảng đã sắp xếp thành một BST cân bằng về chiều cao, ta vận dụng tính chất mảng đã sắp xếp:
Ta áp dụng đệ quy để dựng cây:
Cách này đảm bảo cây luôn cân bằng nhất có thể vì mỗi lần chia đều mảng thành hai nửa
Time and space complexity
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function sortedArrayToBST(nums: number[]): TreeNode | null {
16 function build(l: number, r: number): TreeNode | null {
17 if (l > r) return null;
18 const mid = Math.floor((l + r) / 2)
19 const node = new TreeNode(nums[mid]);
20 node.left = build(l, mid - 1)
21 node.right = build(mid + 1, r)
22 return node;
23 }
24
25 return build(0, nums.length - 1)
26};