Check Full Binary Tree 07/26

A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has one child node. More information about full binary trees can be found here.

Full Binary Tree
      1
     / \
    2   3
   / \
  4   5

Not a Full Binary Tree
      1
     / \
    2   3
   / 
  4   

Example

Given tree {1,2,3}, return true
Given tree {1,2,3,4}, return false
Given tree {1,2,3,4,5} return true

用BFS 层序便利，如果遇到左右儿子有一个为空的，有一个不为空的，就返回false。利用了A^B，如果A是true，B是false，或者A是false，B是true，那么A^B就是true，A和B同时为true或者同时为false,则A^B为false

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the given tree
     * @return: Whether it is a full tree
     */
    public boolean isFullTree(TreeNode root) {
        // write your code here
        if(root == null){
            return true;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        
        while(!queue.isEmpty()){
            
            int size = queue.size();
            
            for (int i = 0; i < size ; ++i ){
                TreeNode node = queue.poll();
                
                if(node.left!= null ^ node.right != null){
                    return false;
                }
                
                if(node.right != null && node.left != null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
                
            } 
        }
        
        return true;
        
        
    }
}