두 갈래 나무의 노드 개수를 구하고, 두 갈래 나무의 깊이(높이)를 구한다.

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;  

    }