求二叉树中的节点个数、求二叉树的深度(高度)

求二叉树中的节点个数、求二叉树的深度(高度)
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;  
    }  
求二叉树中的节点个数、求二叉树的深度(高度)

 


本文转自农夫山泉别墅博客园博客,原文链接:http://www.cnblogs.com/yaowen/p/4389211.html,如需转载请自行联系原作者

上一篇:Linux系统使用普通命令删除不掉的文件处理方法


下一篇:《Web Hacking 101》中的链接整理