1382-二叉搜索树变平衡树
2021/11/20 23:13:44
本文主要是介绍1382-二叉搜索树变平衡树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
如果有多种构造方法,请你返回任意一种。
示例:
输入:root = [1,null,2,null,3,null,4,null,null]
输出:[2,1,3,null,null,null,4]
解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。
提示:
树节点的数目在 1 到 10^4 之间。
树节点的值互不相同,且在 1 到 10^5 之间。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/balance-a-binary-search-tree
python
# 1382.二叉搜索树变平衡树 # 中序递归-数组-转二叉搜索树 class Solution: def balanceBST(self, root: TreeNode) -> TreeNode: res = [] # 中序递归->有序树转数组 def travel(cur: TreeNode): if not cur: return travel(cur.left) res.append(cur.val) travel(cur.right) # 有序数组转平衡二叉树 def buildBalancedBST(nums: [int], left: int, right: int) -> TreeNode: if left > right: return mid = left + int((right-left) >> 1) root = TreeNode(nums[mid]) root.left = buildBalancedBST(nums, left, mid-1) root.right = buildBalancedBST(nums, mid+1, right) return root travel(root) return buildBalancedBST(res, 0, len(res)-1)
golang
package binaryTree // 递归中序生成排序的数组,根据数组左闭右闭递归生成BST func balanceBST(root *TreeNode) *TreeNode { res := []int{} var travel func(cur *TreeNode) var buildBalancedBST func(nums []int, left, right int) *TreeNode travel = func(cur *TreeNode) { if cur == nil { return } travel(cur.Left) res = append(res, cur.Val) travel(cur.Right) } buildBalancedBST = func(nums []int, left, right int) *TreeNode { if left > right { return } var mid int = left + (right - left) >> 1 root := &TreeNode{Val: nums[mid]} root.Left = buildBalancedBST(nums, left, mid-1) root.Right = buildBalancedBST(nums, mid+1, right) return root } travel(root) return buildBalancedBST(res, 0, len(res)-1) }
这篇关于1382-二叉搜索树变平衡树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南