首页 > 其他 > 详细

判断是否是完全二叉树

时间:2017-01-26 00:08:02      阅读:244      评论:0      收藏:0      [点我收藏+]

tag: 二叉树 - 完全二叉树

 

思路: 层次遍历二叉树,一旦某个节点没有左孩子或右孩子,则队列中接下来的节点不能有孩子。

 

package com.zhaochao.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by zhaochao on 17/1/25.
 * wiki definition:
 * A complete binary tree in which every level, except possibly the last level, is completed filled, and all nodes
 * are as far left as possible.
 * 翻译成中文: 一个完全二叉树,除了最后一层外,每层都被节点填满,且最后一层的节点都全部靠左。
 *
 * 解题思路:
 * 完全二叉树具备如下特点,当层次遍历遇到第一个节点且其左孩子为空时,那么该节点的右孩子一定为空,且接下来队列中的节点不会有孩子,
 */
public class JudgeCompleteBT {


    public boolean isCompleteBT(TreeNode root) {

        if(root == null) {
            return true;
        }

        boolean noChild = false;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            TreeNode curr = queue.poll();

            if(curr.left != null) {
                // 如果标记被设置,则Queue中任何元素不应再有子元素。
                if(noChild) {
                    return false;
                }
                queue.offer(curr.left);
            } else {
                // 一旦某元素没有左节点或是右节点,则之后所有的元素都不应有子元素。
                // 并且该元素不可以有右节点.
                noChild = true;
            }

            if(curr.right != null) {
                // 如果标记被设置,则Queue中任何元素不应再有子元素。
                if(noChild) {
                    return false;
                }
                queue.offer(curr.right);
            } else {
                // 一旦某元素没有左节点或是右节点,则之后所有的元素都不应有子元素
                noChild = true;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(3);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node2.right = node4;

        JudgeCompleteBT test = new JudgeCompleteBT();
        boolean result = test.isCompleteBT(root);
        System.out.println(result);
    }
}

  

判断是否是完全二叉树

原文:http://www.cnblogs.com/superzhaochao/p/6350297.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!