9777: AVL树

米浴是一名来自特雷森学院的赛马娘，她正在上数据结构课！ 在数据结构课中，她学习了 AVL 树。AVL 树是一种基于树高的二叉搜索树，二叉树 T 的树高是这么定 义的： 

• 如果 T 是空的，那么 h_T = 0；

• 否则，假设 T 的根为 u，l_su 和 r_su 分别表示 u 的左子树和右子树（都有可能是空的）。此 时，h_T = max(h_lsu , h_rsu ) + 1。

称一颗有根二叉树 T 为AVL树，当且仅当： 

• T 是空的，或者

• 假设 T 的根为 u，u 的左子树和右子树（都有可能是空的）l_su 和 r_su 均为 AVL 树，且 |h_lsu − h_rsu | ≤ 1。

现在，米浴有一颗根为 1 的二叉树，但是这棵树可能不是 AVL 树。为了把这棵树变成一颗 AVL 树，她 可以进行任意多次如下的操作，每次操作在以下三种方式中选择一个： 

• 删除一个叶子。

• 选择一个左子节点为空的节点，并创建一个新顶点作为它的左子节点。

• 选择一个右子节点为空的节点，并创建一个新顶点作为它的右子节点。

她想知道，最少几次操作可以让这棵树变成 AVL 树。