Leetcode 1382. Balance a Binary Search Tree [Python]

本文主要是介绍Leetcode 1382. Balance a Binary Search Tree [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算是BST经典问题。另外一个相关的是面橘色打车软件时被问过：判断一个BST是不是平衡的。回到问题，这题我用了笨办法，把全部节点的value拿出啦，sort之后，每次用最中间的值。以此思路递归。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def balanceBST(self, root: TreeNode) -> TreeNode:self.con = []self.travel(root)self.con.sort()print(self.con)return self.buildBalanBST(self.con)   def travel(self, root):if not root:return self.con.append(root.val)self.travel(root.left)self.travel(root.right)def buildBalanBST(self, q):if not len(q):return if len(q) == 1:root = TreeNode(q[0], None, None)return rootelse:mid = len(q)//2value = q[mid]root = TreeNode(value, None, None)root.left = self.buildBalanBST(q[:mid])root.right = self.buildBalanBST(q[mid+1:])return root

 

这篇关于Leetcode 1382. Balance a Binary Search Tree [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---