判断二叉树是否是完整

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

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

思路

使用队列按层次遍历的顺序进行，使用flag记录上一层的状态，默认为false 即对应第一个遍历到根节点的状态。

flag 与 节点状态对应如下：

• 节点为空  flag = true

• 节点非空 flag = false

  
  

运行思路

• root != null 时，使用队列层次遍历，flag = false;

• 节点为空时，flag = true 标记

• 若节点非空

  • 前一个节点为空时，则该二叉树一定不完整。

    • 判断上一个节点是否为空的方式 flag

      
      

  • 前一个节点非空时，则添加节点用于遍历其子节点即可

    
    

• 若节点为空

  • 前一个节点为空时，记录flag = true; 不操作

  • 前一个节点非空时，记录flag = true; 不操作

  • 以上操作可以合并，即当当前节点为空时，前一个节点是否为空都不需要操作，只需要记录当前节点为空即 flag = true;

    
    

• 由于每个节点有两个左右子节点： 每次循环都要对左右两个子节点进行判断

  
  

若该树是完整的，则只有遍历到最后

1. /**
   
2. * public class TreeNode {
   
3. *   public int key;
   
4. *   public TreeNode left;
   
5. *   public TreeNode right;
   
6. *   public TreeNode(int key) {
   
7. *     this.key = key;
   
8. *   }
   
9. * }
   
10. */
    
11. public class Solution {
    
12.   public boolean isCompleted(TreeNode root) {
    
13.     // Write your solution here
    
14.     if(root == null){
    
15.       return true;
    
16.     }
    
17.     Deque<TreeNode> que = new ArrayDeque<>();
    
18.     que.offer(root);
    
19.     boolean flag = false;
    
20.     while(!que.isEmpty()){
    
21.         TreeNode cur = que.poll();
    
22.         if(cur.left == null){
    
23.           flag = true;
    
24.         }else if(flag){ //不为空时就需要判断前一个节点是否为空，若为空，则不完整
    
25.           return false;
    
26.         }else {
    
27.           que.offer(cur.left);
    
28.         }
    
29. 
    
30.         if(cur.right == null){
    
31.           flag = true;
    
32.         }else if(flag){
    
33.           return false;
    
34.         }else {
    
35.           que.offer(cur.right);
    
36.         }
    
37.     }
    
38.     return true;
    
39.   }
    
40. }

复制代码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：二叉树 represented represents COMPLETELY completed