面试题 04.02. 最小高度树:
给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉搜索树。
样例 1:
给定有序数组:
[-10,-3,0,5,9],
一个可能的答案是:
[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
原题传送门:
https://leetcode.cn/problems/minimum-height-tree-lcci/
分析
- 面对这道算法题目,二当家的陷入了沉思。
- 最小高度,就意味着要尽可能平衡,完全,满。
- 二叉搜索树本来是有一些限制的,但是给的数组已经排好序了,那我们每次从中间分成左右子树,简直完美。
题解
rust
// 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: i32, r: i32) -> Option<Rc<RefCell<TreeNode>>> {
if l > r {
return Option::None;
}
let mid = (l + r) >> 1;
// let mid = (l + r + 1) >> 1;
let mut root = TreeNode::new(nums[mid as usize]);
root.left = dfs(nums, l, mid - 1);
root.right = dfs(nums, mid + 1, r);
return Option::Some(Rc::new(RefCell::new(root)));
}
return dfs(&nums, 0, (nums.len() - 1) as i32);
}
}
go
/**
* 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, int) *TreeNode
dfs = func(nums []int, l int, r int) *TreeNode {
if l > r {
return nil
}
mid := (l + r) >> 1
//mid := (l + r + 1) >> 1
return &TreeNode{
nums[mid],
dfs(nums, l, mid-1),
dfs(nums, mid+1, r),
}
}
return dfs(nums, 0, len(nums)-1)
}
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode* dfs(vector<int>& nums, int l, int r) {
if (l > r) {
return nullptr;
}
int mid = (l + r) >> 1;
// int mid = (l + r + 1) >> 1;
TreeNode *root = new TreeNode(nums[mid]);
root->left = dfs(nums, l, mid - 1);
root->right = dfs(nums, mid + 1, r);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return dfs(nums, 0, nums.size() - 1);
}
};
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
private TreeNode dfs(int[] nums, int l, int r) {
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
// int mid = (l + r + 1) >> 1;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, l, mid - 1);
root.right = dfs(nums, mid + 1, r);
return root;
}
}
typescript
/**
* 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 = function (nums: number[], l: number, r: number): TreeNode | null {
if (l > r) {
return null;
}
const mid = (l + r) >> 1;
//const mid = (l + r + 1) >> 1;
return new TreeNode(
nums[mid],
dfs(nums, l, mid - 1),
dfs(nums, mid + 1, r)
);
};
return dfs(nums, 0, nums.length - 1);
};
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def dfs(l: int, r: int) -> TreeNode:
if l > r:
return None
mid = (l + r) >> 1
# mid = (l + r + 1) >> 1
return TreeNode(
nums[mid],
dfs(l, mid - 1),
dfs(mid + 1, r),
)
return dfs(0, len(nums) - 1)
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~
本文含有隐藏内容,请 开通VIP 后查看