首页 > 其他 > 详细

Check If Binary Tree Is Completed

时间:2020-01-03 09:40:36      阅读:72      评论:0      收藏:0      [点我收藏+]

Check if a given binary tree is completed. A complete binary tree is one in which every level of the binary tree is completely filled except possibly the last level. Furthermore, all nodes are as far left as possible.

Examples

        5

      /    \

    3        8

  /   \

1      4

is completed.

        5

      /    \

    3        8

  /   \        \

1      4        11

is not completed.

Corner Cases

  • What if the binary tree is null? Return true in this case.

How is the binary tree represented?

We use the level order traversal sequence with a special symbol "#" denoting the null node.

For Example:

The sequence [1, 2, 3, #, #, 4] represents the following binary tree:

    1

  /   \

 2     3

      /

    4

 

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public boolean isCompleted(TreeNode root) {
    // Write your solution here
    if (root==null){
      return true;
    }
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.offer(root);
    
    int isLeaf = 0;
    while(!q.isEmpty()){
      Queue<TreeNode> nextQ = new LinkedList<TreeNode>();
      int size = q.size();
      for(int i=0; i<size; i++){
        TreeNode curNode = q.poll();
        if(curNode.left==null && curNode.right!=null){
          return false;
        }
        if(curNode.left!=null){
          if(isLeaf==1){
            return false;
          }
          nextQ.offer(curNode.left);
        }
        if(curNode.right!=null){
          if(isLeaf==1){
            return false;
          }
          nextQ.offer(curNode.right);
        }
        if(curNode.left==null || curNode.right==null){
          isLeaf=1;
        }
      }
      q = nextQ;
    }
    return true;

  }
}

Check If Binary Tree Is Completed

原文:https://www.cnblogs.com/zg1005/p/12142993.html

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