是否存在多个具有相同有序遍历的高度平衡BST

Question

我正在解决这个问题，我很困惑一个输入是否可以有多个答案。

Answer 1

是；如果不是所有的叶子都有相同的深度，那么基本上可以决定在哪里去掉节点(受一些限制(。如果树的节点数不能表示为整数n的2^n-1(在这种情况下^是幂(，则情况就是这样。假设我们有元素1到6：

可能的树

4
/    
2      5
/       
1   3      6

4
/    
2      6
/     /
1   3  5  

3
/    
2      5
/      / 
1      4   6

3
/    
1      5
    / 
2  4   6

Answer 2

完美二叉树的情况

如果数组中元素的数目恰好是"0"；二减一的幂"；，例如1、3、7、15、31等，则相对容易地证明只有一个平衡的二进制搜索树具有相同的有序遍历。实际上，左子树和右子树将需要具有相同数量的元素；因此，根必须是中间元素；并且通过归纳，对于右子树和对于左子树只有一种可能性。

例如，这是唯一一个使用元素[1,2,3,4,5,6,7]:的完整二进制搜索树

4
/   
2     6
/    /  
1   3 5   7

不完全二叉树的情形

如果数组中元素的数目不完全是"0"；二减一的幂"；，那么这棵树就不是完美的；特别地，叶片将有两种可能的深度。这给了我们一点松弛，我们可以利用它来生成多个解决方案。

例如，这是四个使用元素[1,2,3,4,5,6]:的树

3             3             4             4
/            /            /            /   
1     5       2     5       2     5       2     6
   /      /     /      /           /    /  
2 4   6   1     4   6   1   3     6   1   3 5