/**
 * 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> queue = new LinkedList<>();
    boolean flag = false;
    queue.offer(root);

    while (!queue.isEmpty()) {
      TreeNode cur = queue.poll();
      if (cur.left == null) {
        flag = true;
      } else if (flag) {
        return false;
      } else {
        queue.offer(cur.left);
      }

      if (cur.right == null) {
        flag = true;
      } else if (flag) {
        return false;
      } else {
        queue.offer(cur.right);
      }
    }
    return true;
  }
}

approach： 用一个flag来记录 第一次碰见null的情况， 如果往后terminate的时候，遇见非空的子节点，而flag又是true的话，就可以返回false，全部走完，返回true。

worst case的话，就全部节点走了一遍。 O(n)