[数据结构与算法]leetcode 1382. 将二叉搜索树变平衡 【二叉搜索树】

思路：

首先将二叉搜索树由中序遍历得到有序的节点序列。

然后创建一棵平衡二叉树。

code:

# 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:
        def inorder(root):
            if root:
                inorder(root.left)
                nodes.append(root.val)
                inorder(root.right)

        def build_tree(l, r):
            mid = (l + r) // 2
            print(mid)
            node = TreeNode(nodes[mid], None, None)
            if l <= mid - 1:
                node.left = build_tree(l, mid - 1)
            if r >= mid + 1:
                node.right = build_tree(mid + 1, r)
            return node

        nodes = []
        inorder(root)
        return build_tree(0, len(nodes) - 1)