判断二叉树是否为完全二叉树的实例

时间:2021-05-19

完全二叉树特点

完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的。最后一层如果也满了,是一颗满二叉树,也是完全二叉树。最后一层如果不满,缺少的结点也全部的集中在左边,那也是一颗完全二叉树。

判断一棵二叉树是否为完全二叉树

import java.util.*;class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}public class CheckCompletion { public boolean checking(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); boolean leaf = false; // 叶子结点 TreeNode left; TreeNode right; queue.add(root); while (!queue.isEmpty()) { root = queue.poll(); left = root.left; right = root.right; if ((leaf&&(left!=null||right!=null)) || (left==null&&right!=null)) { // 如果之前层遍历的结点没有右孩子,且当前的结点有左或右孩子,直接返回false // 如果当前结点有右孩子却没有左孩子,直接返回false return false; } if (left != null) { queue.offer(root.left); } if (right != null) { queue.offer(root.right); }else { leaf = false; // 如果当前结点没有右孩子,那么之后层遍历到的结点必须为叶子结点 } } return true; }}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章