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

题目描述

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

image-20230306225337693

image-20230306225334773

思路分析

完全二叉树的定义是除了最后一层，其他层都是满的，最后一层如果不满，那么所有节点都必须靠左排列。

  1. 使用队列进行层序遍历。
  2. 遍历过程中，记录是否遇到过空节点。
  3. 如果在遍历过程中遇到空节点后还有非空节点出现，则该树不是完全二叉树。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 // 如果之前遇到过空节点，现在又遇到非空节点
			}
			queue = append(queue, cur.Left, cur.Right) // 将左右子节点加入队列
		}
	}

	return true
}

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2023/00882429
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！