Given the root
of a binary tree, determine if it is a complete binary tree.
In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1
and 2h
nodes inclusive at the last level h
.
Example 1:
Input: root = [1,2,3,4,5,6] Output: true Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: root = [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible.
Constraints:
- The number of nodes in the tree is in the range
[1, 100]
. 1 <= Node.val <= 1000
二叉树的完全性检验。
给定一个二叉树的 root ,确定它是否是一个 完全二叉树 。
在一个 完全二叉树 中,除了最后一个关卡外,所有关卡都是完全被填满的,并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/check-completeness-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是 BFS 层序遍历,我参考了这个帖子。注意题目定义,对于一个完全二叉树,我们只能允许他在最后一行上有缺失 node,同时在每一行上,node 应该尽量往左。这里我们想到 BFS 不难,但是需要抓到 BFS 的重点:BFS 遍历是从上到下,每一层从左往右遍历的。所以当我们遇到一个空节点的时候,如果在遍历结束前再遇到一个非空节点,则说明这棵树不是完全二叉树。
时间O(n)
空间O(n)
Java实现
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public boolean isCompleteTree(TreeNode root) { 18 Queue<TreeNode> queue = new LinkedList<>(); 19 TreeNode prev = root; 20 queue.add(root); 21 while (!queue.isEmpty()) { 22 TreeNode cur = queue.poll(); 23 if (prev == null && cur != null) { 24 return false; 25 } 26 if (cur != null) { 27 queue.add(cur.left); 28 queue.add(cur.right); 29 } 30 prev = cur; 31 } 32 return true; 33 } 34 }
标签:958,TreeNode,cur,val,Binary,二叉树,Completeness,root,left From: https://www.cnblogs.com/cnoodle/p/17218089.html