树
二叉搜索树
数组
分治
二叉树
题目描述
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 平衡 二叉搜索树。
示例 1:
输入: nums = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: [0,-10,5,null,-3,null,9] 也将被视为正确答案:
示例 2:
输入: nums = [1,3]
输出: [3,1]
解释: [1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
按 严格递增 顺序排列
解法
方法一:二分 + 递归
我们设计一个递归函数 $\textit{dfs}(l, r)$,表示当前待构造的二叉搜索树的节点值都在数组 $\textit{nums}$ 的下标范围 $[l, r]$ 内。该函数返回构造出的二叉搜索树的根节点。
函数 $\textit{dfs}(l, r)$ 的执行流程如下:
如果 $l > r$,说明当前数组为空,返回 null
。
如果 $l \leq r$,取数组中下标为 $\textit{mid} = \lfloor \frac{l + r}{2} \rfloor$ 的元素作为当前二叉搜索树的根节点,其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整。
递归地构造当前二叉搜索树的左子树,其根节点的值为数组中下标为 $\textit{mid} - 1$ 的元素,左子树的节点值都在数组的下标范围 $[l, \textit{mid} - 1]$ 内。
递归地构造当前二叉搜索树的右子树,其根节点的值为数组中下标为 $\textit{mid} + 1$ 的元素,右子树的节点值都在数组的下标范围 $[\textit{mid} + 1, r]$ 内。
返回当前二叉搜索树的根节点。
答案即为函数 $\textit{dfs}(0, n - 1)$ 的返回值。
时间复杂度 $O(n)$,空间复杂度 $O(\log n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
Python3 Java C++ Go TypeScript Rust JavaScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 # 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 ]) -> Optional [ TreeNode ]:
def dfs ( l : int , r : int ) -> Optional [ TreeNode ]:
if l > r :
return None
mid = ( l + r ) >> 1
return TreeNode ( nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r ))
return dfs ( 0 , len ( nums ) - 1 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int [] nums ;
public TreeNode sortedArrayToBST ( int [] nums ) {
this . nums = nums ;
return dfs ( 0 , nums . length - 1 );
}
private TreeNode dfs ( int l , int r ) {
if ( l > r ) {
return null ;
}
int mid = ( l + r ) >> 1 ;
return new TreeNode ( nums [ mid ] , dfs ( l , mid - 1 ), dfs ( mid + 1 , r ));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
TreeNode * sortedArrayToBST ( vector < int >& nums ) {
auto dfs = [ & ]( this auto && dfs , int l , int r ) -> TreeNode * {
if ( l > r ) {
return nullptr ;
}
int mid = ( l + r ) >> 1 ;
return new TreeNode ( nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r ));
};
return dfs ( 0 , nums . size () - 1 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST ( nums [] int ) * TreeNode {
var dfs func ( int , int ) * TreeNode
dfs = func ( l , r int ) * TreeNode {
if l > r {
return nil
}
mid := ( l + r ) >> 1
return & TreeNode { nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r )}
}
return dfs ( 0 , len ( nums ) - 1 )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sortedArrayToBST ( nums : number []) : TreeNode | null {
const dfs = ( l : number , r : number ) : TreeNode | null => {
if ( l > r ) {
return null ;
}
const mid = ( l + r ) >> 1 ;
return new TreeNode ( nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r ));
};
return dfs ( 0 , nums . length - 1 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std :: rc :: Rc ;
use std :: cell :: RefCell ;
impl Solution {
pub fn sorted_array_to_bst ( nums : Vec < i32 > ) -> Option < Rc < RefCell < TreeNode >>> {
fn dfs ( nums : & Vec < i32 > , l : usize , r : usize ) -> Option < Rc < RefCell < TreeNode >>> {
if l > r {
return None ;
}
let mid = ( l + r ) / 2 ;
if mid >= nums . len () {
return None ;
}
let mut node = Rc :: new ( RefCell :: new ( TreeNode :: new ( nums [ mid ])));
node . borrow_mut (). left = dfs ( nums , l , mid - 1 );
node . borrow_mut (). right = dfs ( nums , mid + 1 , r );
Some ( node )
}
dfs ( & nums , 0 , nums . len () - 1 )
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function ( nums ) {
const dfs = ( l , r ) => {
if ( l > r ) {
return null ;
}
const mid = ( l + r ) >> 1 ;
return new TreeNode ( nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r ));
};
return dfs ( 0 , nums . length - 1 );
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private int [] nums ;
public TreeNode SortedArrayToBST ( int [] nums ) {
this . nums = nums ;
return dfs ( 0 , nums . Length - 1 );
}
private TreeNode dfs ( int l , int r ) {
if ( l > r ) {
return null ;
}
int mid = ( l + r ) >> 1 ;
return new TreeNode ( nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r ));
}
}
GitHub