将有序数组转换为二叉搜索树

Category	Difficulty	Likes	Dislikes
algorithms	Easy (76.25%)	917	-

Tags

tree | depth-first-search

Companies

airbnb

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

1
2
3
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

Discussion | Solution

解法

 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
39
40
41
// @lc code=start
// 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::cell::RefCell;
use std::rc::Rc;
impl Solution {
    /// ## 解题思路
    /// - 递归
    pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        fn gen(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
            if nums.len() == 0 {
                return None;
            }
            let i = nums.len() / 2;
            Some(Rc::new(RefCell::new(TreeNode {
                val: nums[i],
                left: gen(&nums[..i]),
                right: gen(&nums[(i + 1)..]),
            })))
        }
        gen(&nums)
    }
}
// @lc code=end

 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
class Solution {
public:
    /*
    * ## 解题思路
    * * 递归法
    *   1. 平衡二叉搜索树的左右子树高度差不超过1；
    *   2. 可以推出，平衡二叉搜索树的根节点为有序数组的中间值；
    *   3. 使用有序数组中间数值生成树根节点；
    *   4. 左，右子树为该值左、右两侧数组生成的子平衡二叉搜索树；
    */
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return converVecToBSTRec(nums, 0, nums.size());
    }

    // 递归将有序数组nums中[start, end)的元素转换成平衡二叉搜索树
    TreeNode* converVecToBSTRec(vector<int>& nums, int start, int end) {
        if (start >= end) {  //递归终止条件
            return NULL;
        }
        //数组中间节点为根节点
        int mid = start + (end-start) / 2;
        TreeNode* root = new TreeNode();
        root->val = nums[mid];
        //递归处理左右子树
        root->left = converVecToBSTRec(nums, start, mid);
        root->right = converVecToBSTRec(nums, mid+1, end);

        return root;
    }
};

将有序数组转换为二叉搜索树

将有序数组转换为二叉搜索树

解法

相关文章：