二叉搜索树问题：将一个BST转化为左右节点数相差1的BST

Question

我正在做一个问题，要求我平衡任何二叉搜索树，标准是每一层的左右子树应该有相同数量的节点或最多 1 个节点差异

我该如何解决这个问题？到目前为止，我已经将树转换为链表……仅此而已。我很确定这是第一步，但不太确定。我到处寻找资源，但我能找到的最接近的东西是 day-stout-warren 算法，它基于高度而不是节点数量进行平衡。

我只是在寻找伪代码

Answer 1

中序遍历将所有节点加入一个数组，那么大致应该是这样：


fun buildBalanced(
    array: Array, 
    start: Int = 0, 
    end: Int = array.length) -> Node {
  if (start >= end) {
    return nil
  }
  let middle = (start + end) / 2
  return new Node(
      array[middle], 
      buildBalanced(array, start, middle),
      buildBalanced(array, middle + 1, end))  
}

Answer 2

这是一个 Python 解决方案，它在 O(n) 时间内工作，就地使用 O(h) 辅助 space，其中 h 是树的高度；唯一的辅助数据结构是递归函数所需的堆栈。

它使用一个生成器函数工作，该函数迭代树 而消费者正在更改树，但我们制作 left 和 [=13] 的本地副本=] 子树，然后再生成它们，因此消费者可以在不破坏生成器的情况下重新分配它们。（实际上只需要 right 的本地副本，但无论如何我都制作了本地副本。）

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
    def __repr__(self):
        # display for debug/testing purposes
        def _r(n):
            return '*' if n is None else '(%s ← %r → %s)' % (_r(n.left), n.data, _r(n.right))
        return _r(self)

def balance(root):
    def _tree_iter(node):
        if node is not None:
            # save to local variables, could be reassigned while yielding
            left, right = node.left, node.right
            yield from _tree_iter(left)
            yield node
            yield from _tree_iter(right)
    
    def _helper(it, k):
        if k == 0:
            return None
        else:
            half_k = (k - 1) // 2
            left = _helper(it, half_k)
            node = next(it)
            right = _helper(it, k - half_k - 1)
            node.left = left
            node.right = right
            return node
    
    n = sum(1 for _ in _tree_iter(root))
    return _helper(_tree_iter(root), n)

示例：

>>> root = Node(4, left=Node(3, left=Node(1, right=Node(2))), right=Node(6, left=Node(5), right=Node(8, left=Node(7), right=Node(9))))
>>> root
(((* ← 1 → (* ← 2 → *)) ← 3 → *) ← 4 → ((* ← 5 → *) ← 6 → ((* ← 7 → *) ← 8 → (* ← 9 → *))))
>>> balance(root)
(((* ← 1 → *) ← 2 → (* ← 3 → (* ← 4 → *))) ← 5 → ((* ← 6 → *) ← 7 → (* ← 8 → (* ← 9 → *))))

二叉搜索树问题：将一个BST转化为左右节点数相差1的BST

Binary search tree problem: transform a BST into a BST where the number of nodes differ by 1 between the left and right

data-structures

binary-tree

binary-search-tree

graph-theory

balance