Proof. [stack-permutation-000G]

注意到为使有效长度最大, 相应的二叉树中的右节点个数和回溯次数要尽可能多. 同时满足这两个要求意味着 $(i)$ 除根节点外至少有一个左结点 ¹. $(ii)$ 该二叉树必有一个位于根节点右侧的节点 ². 如下图所示

由此出发, 我们将剩余的所有 $n-3$ 个节点全部添加到树中唯一的左节点的右侧. 即

下面我们只需算出 $\ell(M)$, 便可得到 $\ell_n$ 的最大值. 不妨直接写出 $h(M)$

立刻看出 $\ell(M) = 2 + 2(n-3) + (n-2) + 2 = 3n-4$.