扣丁学堂Java培训告诉你如何判断二叉树是否为完全二叉树

2018-05-09 11:55:05 811浏览

         近日有小伙伴询问扣丁学堂的咨询老师关于二叉树方面的问题，小编发现有不少的小伙伴不知道如何判断二叉树是否为完全二叉树，现在小编就给大家分享一下扣丁学堂Java在线学习讲述的判断二叉树是否为完全二叉树的实例。

完全二叉树特点

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

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

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;
  }
}

         以上就是扣丁学堂Java培训小编为大家分享的如何判断二叉树是否为完全二叉树，希望对小伙伴们有所帮助，想要了解更多内容的小伙伴可以登录扣丁学堂官网咨询，扣丁学堂是专业的Java培训机构，不仅有专业的老师和与时俱进的课程体系，还有大量的Java视频教程供学员观看学习哦。Java技术交流群：670348138。

【关注微信公众号免费领取丁豆获取更多学习资料】

查看更多关于“Java开发资讯”的相关文章>>