二叉树家谱校验代码为何无法通过部分测试用例

常规测试用例不通过的常见原因 #

• 空指针处理逻辑错误：未对叶子节点的空左右子节点做判空处理，直接读取age属性触发空指针异常；或把空节点误判为非法状态，提前返回错误结果。
• 分支遍历遗漏：递归/遍历逻辑只覆盖了左子树或右子树单侧分支，另一侧节点完全没做校验，导致深层非法节点漏检。
• 比较逻辑不符合要求：要么把大小关系写反（误判子节点年龄大于父节点为合法），要么用了>=/<=做非严格比较，没有覆盖「子节点年龄必须严格小于父节点」的规则，父子年龄相等的场景会误判为合法。
• 提前返回逻辑错误：遍历到第一个符合要求的节点就直接返回true，没有走完所有节点的校验流程，深层存在非法节点时无法识别。
• 额外添加题目未要求的校验规则：比如自行增加「年龄必须大于0」「节点年龄不能超过120」这类题目没提到的判断，导致合法输入被误判。

性能测试用例不通过的常见原因 #

• 时间复杂度退化：写出带重复遍历的逻辑，比如每到一个节点就遍历整棵子树做校验，时间复杂度从最优的O(n)退化到O(n²)，节点规模大时直接超时。
• 递归实现栈溢出：如果测试用例是高度倾斜的单链二叉树（比如所有节点都只有左子节点，树深达到万级以上），递归实现受JVM默认栈深度限制会抛出StackOverflowError，无法通过大深度用例。
• 内存占用过高：遍历过程中把整棵树的所有节点都存入冗余集合做二次处理，没有做到边遍历边校验，大样本下触发内存溢出。

参考正确实现（兼顾逻辑正确性与性能） #

import java.util.Deque;
import java.util.LinkedList;

public class FamilyTreeValidator {
    public boolean isValid(TreeNode root) {
        // 空树按题目规则默认合法，若题目有特殊要求可调整返回值
        if (root == null) {
            return true;
        }
        // 迭代式深度优先遍历，避免递归栈溢出问题，时间复杂度O(n)，空间复杂度O(h)，h为树高
        Deque<TreeNode> traverseStack = new LinkedList<>();
        traverseStack.push(root);
        while (!traverseStack.isEmpty()) {
            TreeNode currentNode = traverseStack.pop();
            // 校验左子节点
            if (currentNode.left != null) {
                if (currentNode.left.age >= currentNode.age) {
                    return false;
                }
                traverseStack.push(currentNode.left);
            }
            // 校验右子节点
            if (currentNode.right != null) {
                if (currentNode.right.age >= currentNode.age) {
                    return false;
                }
                traverseStack.push(currentNode.right);
            }
        }
        return true;
    }

    // 题目给定的TreeNode结构
    class TreeNode {
        int age;
        TreeNode left;
        TreeNode right;
    }
}

提示：如果你用的是递归实现，可以对照上面的错误点检查是否存在漏判分支、比较逻辑错误的问题；如果逻辑没问题但性能不通过，换成迭代遍历即可解决栈溢出和大部分性能问题。

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