求视觉化解释：如何通过替换叶节点将高度n的二叉树扩展为高度n+1的二叉树？

引用《形式语言与自动机导论》（Peter Linz）中的表述：“要从高度为n的二叉树得到高度为n+1的二叉树，我们最多可以将每个原有叶节点替换为两个叶节点。”

首先明确二叉树高度的定义：这里的高度指根节点到最远叶节点的路径边数——比如只有根节点的树高度为0，根带两个子节点的树高度为1。

示例1：从高度0到高度1 #

1. 初始高度0的树：只有1个根节点（它本身就是叶节点）

O

2. 替换叶节点：把这个根节点（唯一的叶节点）替换成两个子节点，此时根到新叶节点的路径有1条边，树的高度变为1：

O
   / \
  O   O

示例2：从高度1到高度2 #

1. 初始高度1的树：根节点带两个叶节点子节点

O
   / \
  O   O

2. 替换所有叶节点：把这两个叶节点各自替换成两个子节点，此时根到新叶节点的路径有2条边，树的高度变为2：

O
     / \
    O   O
   / \ / \
  O O O O

核心逻辑 #

• 替换叶节点是提升高度的关键：原有树的最远叶节点距离根有n条边，替换它为两个子节点后，新叶节点距离根就有n+1条边，直接把树的最大高度拉到n+1。
• 所谓“最多”替换：如果只替换部分叶节点，树的高度也能达到n+1，但只有替换所有叶节点时，得到的是同高度下节点数最多的满二叉树，这就是原文中“最多”的含义。

内容的提问来源于stack exchange，提问作者Tryer outer