Check whether a given Binary Tree is Complete or not 解答

Question

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Solution 1 -- BFS

Using BFS and a flag.

 1 public class Solution {
 2     public boolean checkCompleteBinaryTree(TreeNode root) {
 3         // BFS
 4         // flag whether means previous node has both children
 5         boolean flag = true;
 6         List<TreeNode> current = new ArrayList<TreeNode>();
 7         List<TreeNode> next;
 8         current.add(root);
 9 
10         while (current.size() > 0) {
11             next = new ArrayList<TreeNode>();
12             for (TreeNode node : current) {
13                 if (!flag && (node.left != null || node.right != null))
14                     return false;
15                 if (node.left == null && node.right != null)
16                     return false;
17                 if (node.left != null) {
18                     next.add(node.left);
19                     if (node.right != null) {
20                         next.add(node.right)
21                         flag = true;
22                     } else {
23                         flag = false;
24                     }
25                 }
26             }
27             current = next;
28         }
29 
30         return true;
31     }
32 }

Solution 2 -- Recursive

Using recursion