【二叉树】将二叉搜索树变平衡

0x00 题目

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树
新生成的树应该与原来的树有着相同的节点值
如果有多种构造方法，请你返回任意一种

如果一棵二叉搜索树中
每个节点的两棵子树高度差不超过 1
我们就称这棵二叉搜索树是 平衡的

---

0x01 思路

通过对二叉搜索树进行中序遍历
得到一个升序数组
再通过升序数组构建平衡二叉树
取数组中间的数，生成根节点
则数组左右两边的的数量差值不会超过 1
递归地对左右两部分进行构建即可

---

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func balanceBST(_ root: TreeNode?) -> TreeNode? {
    var arr: [Int] = []
    
    // 中序遍历
    func dfs(_ root: TreeNode?) {
        guard let r = root else { return }
        dfs(r.left)
        arr.append(r.val)
        dfs(r.right)
    }
    
    // 构建平衡二叉树
    func build(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
        if left > right { return nil }
        // 取中值
        let mid = (left + right) / 2
        let val = nums[mid]
        
        let node = TreeNode(val)
        // 递归构建
        node.left = build(nums, left, mid-1)
        node.right = build(nums, mid+1, right)
        return node
    }
    
    dfs(root)
    
    let node = build(arr, 0, arr.count-1)
    return node
}

---

0x03 我的小作品

欢迎体验我的作品之一：小笔记-XNote
做笔记，一步到位！
传笔记，一键到位！
App Store 搜索即可~

---