LeetCode 补充题 204. 二叉搜索树与完全二叉树的判定

约 5 分钟
文章信息 2 个分类 4 个标签
分类
补充题 中等
标签
深度优先搜索 树 二叉树 二叉搜索树

题目描述

[!green]

牛客原题： ✅ 补充题 204. 二叉搜索树与完全二叉树的判定

给定二叉树 root，返回 [是否为二叉搜索树, 是否为完全二叉树]。

搜索树左右子树必须严格小于、严格大于根值；完全树的最后一层从左侧连续填充。

示例 1：

输入： root = [1,null,2]
输出： [true,false]

提示：

  • 空树的两项结果都为 true。
  • 节点值为 32 位整数。

题意分析

二叉搜索树约束整棵子树的值域，完全二叉树约束节点在各层的位置。两种性质互不推出，需要独立判定，并按题目指定顺序返回两个布尔值。

解法：递归边界检查 + 层序遍历

核心思路

[!blue]

两项判定解决不同约束，不应合成一个模糊的“合法树”条件。

搜索树判定把允许的严格上下界随递归下传：进入左子树收紧上界，进入右子树收紧下界。只比较直接孩子不够，祖先给出的限制也必须一直保留。

完全树判定按层保留空孩子位置。第一次遇到空位后，后面只能继续为空；再出现真实节点就说明最后一层没有靠左填满。

例如只有根 1 和右孩子 2，大小关系满足搜索树要求，但左侧已有空位，完全树判定为 false。两项独立计算，再按约定顺序返回。

解题步骤

  1. 搜索树检查向下传递严格上下界。
  2. 完全树检查层序遍历中出现空位后不得再出现非空节点。
  3. 两项独立计算。

代码实现

class Solution {
    public boolean[] classifyTree(TreeNode root) {
        return new boolean[] {
            isValidBST(root),
            isCompleteTree(root)
        };
    }

    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }

        if (node.val <= lower || node.val >= upper) {
            return false;
        }

        return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
    }

    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        boolean seenNull = false;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (node == null) {
                seenNull = true;
                continue;
            }

            if (seenNull) {
                return false;
            }

            queue.offer(node.left);
            queue.offer(node.right);
        }

        return true;
    }
}

func isValidBST(root *TreeNode) bool {
    return validateBST(root, nil, nil)
}

func validateBST(node *TreeNode, lower *int, upper *int) bool {
    if node == nil {
        return true
    }
    if lower != nil && node.Val <= *lower {
        return false
    }
    if upper != nil && node.Val >= *upper {
        return false
    }
    return validateBST(node.Left, lower, &node.Val) && validateBST(node.Right, &node.Val, upper)
}

func isCompleteTree(root *TreeNode) bool {
    queue := []*TreeNode{
        root,
    }
    seenNull := false

    for head := 0; head < len(queue); head++ {
        node := queue[head]
        if node == nil {
            seenNull = true
            continue
        }
        if seenNull {
            return false
        }
        queue = append(queue, node.Left, node.Right)
    }
    return true
}

func classifyTree(root *TreeNode) []bool {
    return []bool{
        isValidBST(root),
        isCompleteTree(root),
    }
}

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

关键点总结

[!green]

搜索树检查向下传递严格上下界；完全树检查层序遍历中出现空位后不得再出现非空节点。两项独立计算。

易错点总结

[!yellow]

  • 搜索树不能只比较父子节点，祖先传下来的上下界也必须满足。
  • 大小关系严格，重复值不能通过；Java 用 long 上下界以允许 int 极值节点。
  • 完全树检查必须保留空孩子位置，否则无法识别左侧空缺后又出现节点。Java 此处使用支持 null 的 LinkedList 队列。
  • 空树两项均为 true，返回顺序是搜索树判定、完全树判定。

相似题目

题目 难度 关联与区别
98. 验证二叉搜索树 中等 严格上下界判定二叉搜索树的部分相同；本题还独立判定完全二叉树，搜索树成立不代表完全树成立。
958. 二叉树的完全性检验 中等 复用层序检查空位之后不能再出现非空节点的完全树判定；本题另外独立验证二叉搜索树的严格大小关系。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/316047656621
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！