现有Swift实现无法正确识别平衡二叉树的原因是什么

核心逻辑缺陷 #

你的代码仅覆盖了两类边界校验逻辑：

• 节点只有左孩子时，限制左孩子不能再拥有子节点
• 节点只有右孩子时，限制右孩子不能再拥有子节点

完全缺失了平衡二叉树最核心的校验规则：当节点同时存在左右子树时，需要校验左右子树的高度差是否不超过1，这是代码运行错误的根本原因。

失败用例执行过程拆解 #

测试用例 [1, 2, 2, 3, 3, null, null, 4, 4] 结构如下：

1
     /   \
    2     2
   / \
  3   3
 / \
4   4

该树本身是不平衡的：根节点1的左子树高度为3，右子树高度为1，高度差为2，不符合平衡二叉树要求。

代码执行流程如下：

1. 访问根节点1，同时存在左孩子2和右孩子2，代码直接递归校验两个子节点，未校验两者高度差
2. 校验右孩子2：无任何子节点，直接返回true
3. 校验左孩子2：同时存在左孩子3和右孩子3，代码直接递归校验两个子节点，未校验两者高度差
4. 校验左孩子2的右孩子3：无任何子节点，返回true
5. 校验左孩子2的左孩子3：同时存在左孩子4和右孩子4，代码直接递归校验两个子节点，未校验两者高度差
6. 两个4均为叶子节点，全部返回true
7. 所有递归校验通过，代码最终返回true，与预期结果false不符，用例执行失败。

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