完全二叉树节点数与平衡二叉树验证

完全二叉树的节点个数（LeetCode 222）

完全二叉树最后一层节点从左往右排列。利用这一性质，可以 O(log²n) 解决，远优于 O(n) 暴力。

思路：左右深度比较

• 每次计算左子树最左深度 lh、右子树最左深度 rh
• 若 lh == rh：左子树是满二叉树，节点数 = (1 << lh) - 1，递归右子树
• 若 lh != rh：右子树是满二叉树（少一层），递归左子树

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = 0, rh = 0;
    TreeNode l = root, r = root;
    while (l != null) { lh++; l = l.left; }
    while (r != null) { rh++; r = r.right; }
    if (lh == rh) return (1 << lh) - 1;          // 满二叉树
    return 1 + countNodes(root.left) + countNodes(root.right);
}

时间复杂度：O(log²n)，每层调用 O(log n) 次，每次深度计算 O(log n)。

平衡二叉树（LeetCode 110）

平衡二叉树：每个节点的左右子树高度差不超过 1。

解法一：自顶向下（O(n²)，有重复计算）

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int diff = Math.abs(height(root.left) - height(root.right));
    return diff <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

解法二：自底向上 O(n)（推荐）

后序遍历，一旦发现不平衡就返回 -1 剪枝。

public boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

private int checkHeight(TreeNode node) {
    if (node == null) return 0;
    int lh = checkHeight(node.left);
    if (lh == -1) return -1;
    int rh = checkHeight(node.right);
    if (rh == -1) return -1;
    if (Math.abs(lh - rh) > 1) return -1;
    return 1 + Math.max(lh, rh);
}

完全二叉树插入器（LeetCode 919）

在完全二叉树中插入节点，保持完全二叉树性质。

class CBTInserter {
    private Deque<TreeNode> deque = new ArrayDeque<>();
    private TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null || node.right == null) deque.offer(node);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }

    public int insert(int val) {
        TreeNode parent = deque.peek();
        TreeNode child = new TreeNode(val);
        deque.offer(child);
        if (parent.left == null) {
            parent.left = child;
        } else {
            parent.right = child;
            deque.poll();   // 父节点已满，出队
        }
        return parent.val;
    }

    public TreeNode get_root() { return root; }
}

关键总结