private static class TreeNode {  
        int val;  
        TreeNode left;  
        TreeNode right;  
   
        public TreeNode(int val) {  
            this.val = val;  
        }  
    }  
   
    /** 
     * 求二叉树中的节点个数递归解法： O(n) 
     * （1）如果二叉树为空，节点个数为0  
     * （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 
     *            右子树节点个数 + 1 
     */ 
    public static int getNodeNumRec(TreeNode root) {  
        if (root == null) {  
            return 0;  
        } else {  
            return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;  
        }  
    }  
       
    /** 
     *  求二叉树中的节点个数迭代解法O(n)：基本思想同LevelOrderTraversal， 
     *  即用一个Queue，在Java里面可以用LinkedList来模拟  
     */ 
    public static int getNodeNum(TreeNode root) {  
        if(root == null){  
            return 0;  
        }  
        int count = 1;  
        Queue<TreeNode> queue = new LinkedList<TreeNode>();  
        queue.add(root);  
           
        while(!queue.isEmpty()){  
            TreeNode cur = queue.remove();      // 从队头位置移除  
            if(cur.left != null){           // 如果有左孩子，加到队尾  
                queue.add(cur.left);  
                count++;  
            }  
            if(cur.right != null){      // 如果有右孩子，加到队尾  
                queue.add(cur.right);  
                count++;  
            }  
        }  
           
        return count;  
    }  
   
    /** 
     * 求二叉树的深度（高度） 递归解法： O(n) 
     * （1）如果二叉树为空，二叉树的深度为0  
     * （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 
     */ 
    public static int getDepthRec(TreeNode root) {  
        if (root == null) {  
            return 0;  
        }  
   
        int leftDepth = getDepthRec(root.left);  
        int rightDepth = getDepthRec(root.right);  
        return Math.max(leftDepth, rightDepth) + 1;  
    }  
       
    /** 
     * 求二叉树的深度（高度） 迭代解法： O(n) 
     * 基本思想同LevelOrderTraversal，还是用一个Queue 
     */ 
    public static int getDepth(TreeNode root) {  
        if(root == null){  
            return 0;  
        }  
           
        int depth = 0;                          // 深度  
        int currentLevelNodes = 1;      // 当前Level，node的数量  
        int nextLevelNodes = 0;         // 下一层Level，node的数量  
           
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();  
        queue.add(root);  
           
        while( !queue.isEmpty() ){//循环中队列仅包含当前层的节点
            TreeNode cur = queue.remove();      // 从队头位置移除  
            currentLevelNodes--;            // 减少当前Level node的数量  
            if(cur.left != null){               // 如果有左孩子，加到队尾  
                queue.add(cur.left);  
                nextLevelNodes++;           // 并增加下一层Level node的数量  
            }  
            if(cur.right != null){          // 如果有右孩子，加到队尾  
                queue.add(cur.right);  
                nextLevelNodes++;  
            }  
               
            if(currentLevelNodes == 0){ // 说明已经遍历完当前层的所有节点  
                depth++;                       // 增加高度  
                currentLevelNodes = nextLevelNodes;     // 初始化下一层的遍历  
                nextLevelNodes = 0;  
            }  
        }  
           
        return depth;  
    }