基本规律

我们主要是通过左右子树的数量来判断二叉判定树的形态的。而左右子树的数量取决了二分查找中 mid 的取法和节点的数量。

当节点数量为奇数的时候，左右子树的节点数量一定是相同的。当节点数量为偶数时，左右子树的节点数量一定是不同的，此时的节点数量的大小关系取决于 mid 的取法。

我们有两种主流的 mid 取法：

1. ${\displaystyle \text{mid}=\lfloor \frac{l+r}{2}\rfloor }$。这种取法会导致左子树小于右子树；
2. ${\displaystyle \text{mid}=\lceil \frac{l+r}{2}\rceil }$。这种取法会导致右子树小于左子树；

于是对于一棵二叉树，我们通过得出 mid 的取法来判断当前二叉树是不是合法的。

实例

“23” (“教材”, p. 298) (pdf)