[binary tree] balance the binary search tree

0x00 subject

Here's a binary search tree , Please return to a tree After balancing Binary search tree of
The newly generated tree should be different from the original tree same Node values
If there are multiple construction methods , Please return Any one

If a binary search tree
Two subtrees of each node Height difference No more than 1
We call this binary search tree The balance of

---

0x01 Ideas

Through the binary search tree In the sequence traversal
Get one Ascending array
Then build a balanced binary tree through an ascending array
Take an array middle Number of numbers , Generate root node
Then the number of left and right sides of the array Difference value Not more than 1
recursive Just build the left and right parts

---

0x02 solution

Language ：Swift

Tree node ：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
    }
}

solution ：

func balanceBST(_ root: TreeNode?) -> TreeNode? {
    var arr: [Int] = []
    
    //  In the sequence traversal 
    func dfs(_ root: TreeNode?) {
        guard let r = root else { return }
        dfs(r.left)
        arr.append(r.val)
        dfs(r.right)
    }
    
    //  Build a balanced binary tree 
    func build(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
        if left > right { return nil }
        //  Take the median 
        let mid = (left + right) / 2
        let val = nums[mid]
        
        let node = TreeNode(val)
        //  Recursively build 
        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 My little work

Welcome to experience one of my works ： Little notes -XNote
Make notes , One step in place ！
Pass notes , One click ！
App Store Search ~

---