LeetCode: 1382. Balance a Binary Search Tree

微信扫一扫,分享到朋友圈

LeetCode: 1382. Balance a Binary Search Tree

原题地址: https://leetcode.com/problems/balance-a-binary-search-tree/

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
/ \
-3   9
/   /
-10  5

先得到节点组成的有序数组,然后将有序数组转换为平衡二叉搜索树

先通过 中序遍历
将一个 BST 转换为一个有序数组,然后再用二分法把一个有序数组转换为一个平衡二叉树:

  • 将数组从中间切分,
  • 中间那个数是根节点,
  • 左边的数组是左子节点构成的数组,
  • 右边的数组是右子节点构成的数组,
  • 按同样的方法切分左边数组和右边数组。

中序遍历的 Python 代码类似这样:

def inorder(root):
if root is None:
return
inorder(root.left)
# print(root)
inorder(root.right)

这个方法的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def balanceBST(self, root):
self.nodes = []
self.inorder(root)
root = self.buildBST(self.nodes, 0, len(self.nodes) - 1)
return root
def buildBST(self, nodes, min_index, max_index):
if min_index > max_index:
return
mid_index = min_index + (max_index - min_index)/2
root = nodes[mid_index]
root.left = self.buildBST(nodes, min_index, mid_index - 1)
root.right = self.buildBST(nodes, mid_index + 1, max_index)
return root
def inorder(self, root):
if root is None:
return
self.inorder(root.left)
self.nodes.append(root)
self.inorder(root.right)

LeetCode: 108. Convert Sorted Array to Binary Search Tree

上一篇

Java:100==100为true,1000==1000也可以为true!

下一篇

你也可能喜欢

LeetCode: 1382. Balance a Binary Search Tree

长按储存图像,分享给朋友