1382. 将二叉搜索树变平衡

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/balance-a-binary-search-tree/
Star
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
如果有多种构造方法，请你返回任意一种。
示例：
notion imagenotion image
notion imagenotion image
输入：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 之间。
通过次数13,164提交次数18,615

法1 暴力

思路
先存储节点，然后再建立平衡二叉搜索树。参考
🎗️
108. 将有序数组转换为二叉搜索树
题解
# 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:
        res = []
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                res.append(root.val)
                root = root.right
        # print(res)
        return self.build_tree(res)

    def build_tree(self, arr):
        if len(arr) == 0:
            return None
        if len(arr) == 1:
            return TreeNode(arr[0])
        
        idx = len(arr) // 2
        root = TreeNode(arr[idx])
        root.left = self.build_tree(arr[0:idx])
        root.right = self.build_tree(arr[idx+1:])

        return root