二叉树指定层lev节点值唯一性验证：能否无需数据结构实现？

好问题！答案是可以不使用任何显式的栈、列表或集合等辅助数据结构来实现这个需求，当然也有更高效的使用辅助结构的方案。下面分别给出两种场景的递归实现（假设二叉树节点类BinaryTree已定义val、left、right属性）：

方案1：使用辅助集合（高效实现） #

这是常规的最优解，借助集合来跟踪目标层已出现的节点值，遍历过程中一旦发现重复就直接返回结果。

public class BinaryTree {
    int val;
    BinaryTree left;
    BinaryTree right;
    // 已有构造方法及其他实现

    public static boolean isLevelAllUnique(BinaryTree root, int targetLevel) {
        Set<Integer> seenValues = new HashSet<>();
        return traverseAndCheck(root, 0, targetLevel, seenValues);
    }

    private static boolean traverseAndCheck(BinaryTree node, int currentLevel, int targetLevel, Set<Integer> seen) {
        if (node == null) {
            return true; // 空节点不影响唯一性检查
        }
        if (currentLevel == targetLevel) {
            // 尝试将值加入集合，add返回false说明值已存在
            if (!seen.add(node.val)) {
                return false;
            }
            return true;
        }
        // 递归遍历左右子树，只要一侧返回false就整体不满足条件
        return traverseAndCheck(node.left, currentLevel + 1, targetLevel, seen)
                && traverseAndCheck(node.right, currentLevel + 1, targetLevel, seen);
    }
}

说明 #

• 时间复杂度：O(n)，其中n是二叉树总节点数，每个节点最多被遍历一次；
• 空间复杂度：O(k)，k是目标层的节点数，集合最多存储目标层所有不重复的值；
• 逻辑清晰，效率高，适合大多数场景。

方案2：不使用任何辅助数据结构（纯递归实现） #

这个方案完全依靠递归调用栈（语言层面自动管理，不算题目禁止的“数据结构”），通过两次递归遍历实现：第一次遍历目标层的每个节点，第二次遍历整个树检查当前节点的值在目标层是否有重复（排除自身）。

public class BinaryTree {
    int val;
    BinaryTree left;
    BinaryTree right;
    // 已有构造方法及其他实现

    public static boolean isLevelAllUniqueNoAuxDS(BinaryTree root, int targetLevel) {
        // 遍历树的每个节点，对目标层的节点逐一检查重复
        return checkEachTargetNode(root, 0, targetLevel, root);
    }

    // 遍历所有节点，找到目标层的节点并触发重复检查
    private static boolean checkEachTargetNode(BinaryTree currentNode, int currentLevel, int targetLevel, BinaryTree root) {
        if (currentNode == null) {
            return true;
        }
        if (currentLevel == targetLevel) {
            // 检查当前节点的值在目标层是否存在重复（排除自己）
            if (!hasNoDuplicateInLevel(root, 0, targetLevel, currentNode.val, currentNode)) {
                return false;
            }
        }
        return checkEachTargetNode(currentNode.left, currentLevel + 1, targetLevel, root)
                && checkEachTargetNode(currentNode.right, currentLevel + 1, targetLevel, root);
    }

    // 检查目标层中是否存在与targetVal相同且不是excludeNode的节点
    private static boolean hasNoDuplicateInLevel(BinaryTree node, int currentLevel, int targetLevel, int targetVal, BinaryTree excludeNode) {
        if (node == null) {
            return true;
        }
        if (currentLevel == targetLevel) {
            // 找到重复节点（不是自身）
            if (node.val == targetVal && node != excludeNode) {
                return false;
            }
            return true;
        }
        return hasNoDuplicateInLevel(node.left, currentLevel + 1, targetLevel, targetVal, excludeNode)
                && hasNoDuplicateInLevel(node.right, currentLevel + 1, targetLevel, targetVal, excludeNode);
    }
}

说明 #

• 时间复杂度：O(n^2)，每个目标层节点都会触发一次全树遍历，适合节点数较少的二叉树；
• 空间复杂度：O(h)，h是树的高度，仅占用递归调用栈的空间；
• 完全不依赖任何显式辅助数据结构，符合题目要求的“不使用栈、列表等任何数据结构”的限制。

内容的提问来源于stack exchange，提问作者x-devel