铁路网站建设,河北住房建设厅网站首页,字体大全100种,鼎豪网站建设高度平衡的二叉搜索树#xff08;平衡二叉树#xff09;#xff0c;定义见此Leetbook。简单来说#xff0c;就是基于相同节点值构建出来的二叉搜索树中高度最小的#xff0c;即为平衡二叉树#xff08;不唯一#xff09;。有 N 个节点的平衡二叉搜索树#xff0c;它的高…高度平衡的二叉搜索树平衡二叉树定义见此Leetbook。简单来说就是基于相同节点值构建出来的二叉搜索树中高度最小的即为平衡二叉树不唯一。有 N 个节点的平衡二叉搜索树它的高度是 logN 。并且每个节点的两个子树的高度不会相差超过 1。
110. 平衡二叉树
class Solution:def isBalanced(self, root: TreeNode) - bool:def height(node: TreeNode) - int:if not node:return 0leftHeight height(node.left)rightHeight height(node.right)if leftHeight -1 or rightHeight -1 or abs(leftHeight - rightHeight) 1:return -1else:return max(leftHeight, rightHeight) 1return height(root) 0自底向上的递归类似于后序遍历此节点不平衡或者其左子树或右子树不平衡就都返回-1否则返回树的高度。
108. 将有序数组转换为二叉搜索树面试题 04.02. 最小高度树
class Solution:def sortedArrayToBST(self, nums: List[int]) - TreeNode:if not nums:return Nonemid len(nums) // 2root TreeNode(nums[mid])root.left self.sortedArrayToBST(nums[:mid])root.right self.sortedArrayToBST(nums[mid1:])return root从有序递增数组创建一棵高度平衡的二叉搜索树、或平衡二叉树、或高度最小的二叉搜索树。方法是每次取中位数创建节点然后左边比它小的是左子树右边比它大的是右子树递归。此题思路写法都和从遍历序列构造二叉树很像可以参考一下。
1382. 将二叉搜索树变平衡
class Solution:def balanceBST(self, root: TreeNode) - TreeNode:def inorder(node: TreeNode):if not node:return Noneinorder(node.left)nums.append(node.val)inorder(node.right)nums []inorder(root)def creatBST(numlist) - TreeNode:if not numlist:return Nonemid len(numlist) // 2node TreeNode(numlist[mid])node.left creatBST(numlist[:mid])node.right creatBST(numlist[mid1:])return nodereturn creatBST(nums)与上一题思路一样只不过这里需要我们自己对二叉树进行中序遍历得到递增序列再将数组转换为平衡二叉树。这题的官方题解给出了贪心的证明。
