LeetCode 958. 二叉树的完全性检验

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 958. 二叉树的完全性检验

思路分析

层序遍历

参考代码

func isCompleteTree(root *TreeNode) bool {
	if root == nil {
		return true
	}

	queue := []*TreeNode{root}
	end := false // 标记是否遇到空节点

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]

		if cur == nil {
			end = true // 遇到空节点
		} else {
			if end {
				return false // 如果之前遇到过空节点，现在又遇到非空节点，返回 false
			}
			queue = append(queue, cur.Left, cur.Right)
		}
	}
	return true
}

func isCompleteTree(root *TreeNode) bool {
	if root == nil {
		return true
	}

	type Pair struct {
		node  *TreeNode
		index int
	}

	queue := []Pair
	var count int
	var lastIndex int

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		node, index := cur.node, cur.index

		count++
		lastIndex = index

		// 左子节点编号为 2 * index
		if node.Left != nil {
			queue = append(queue, Pair{node.Left, 2 * index})
		}
		// 右子节点编号为 2 * index + 1
		if node.Right != nil {
			queue = append(queue, Pair{node.Right, 2*index + 1})
		}
	}

	// 如果最后一个节点编号 == 节点总数，则说明是完全二叉树。
	return count == lastIndex
}

时间复杂度：O(n)，每个节点访问一次。

空间复杂度：O(n)，队列最多存储所有节点。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/00882429