树的最大深度

递归实现

    /**
     * 求最大深度(递归实现)
     */
    public int maxLengh(TreeNode root){
        if(null == root){
            return 0;
        }

        int left = maxLengh(root.left);
        int right = maxLengh(root.right);
        return Math.max(left,right) + 1;
    }

非递归实现

    /**
     * 求最大深度(层次遍历)
     */
    public int maxLengh2(TreeNode root){
        if(null == root){
            return 0;
        }

        Queue<TreeNode> queue = new ArrayDeque();
        queue.offer(root);

        int level = 0;
        while(!queue.isEmpty()){
            level++;

            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();

                if(null != node.left){
                    queue.offer(node.left);
                }
                if(null != node.right){
                    queue.offer(node.right);
                }
            }
        }
        return level;
    }

树的最小深度

递归实现

    /**
     * 求最小深度(递归)
     */
    public int minLengh(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        if(root.left != null && root.right == null){
            return minLengh(root.left) + 1;
        }
        if(root.left == null && root.right != null){
            return minLengh(root.right) + 1;
        }

        int left = minLengh(root.left);
        int right = minLengh(root.right);
        return Math.min(left, right) + 1;
    }

非递归实现

    /**
     * 求最小深度(层次遍历)
     */
    public int minLengh2(TreeNode root){
        if(null == root){
            return 0;
        }

        Queue<TreeNode> queue = new ArrayDeque();
        queue.offer(root);

        int level = 0;
        while(!queue.isEmpty()){
            level++;

            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();

                if(node.left == null && node.right == null){
                    return level;
                }

                if(null != node.left){
                    queue.offer(node.left);
                }
                if(null != node.right){
                    queue.offer(node.right);
                }
            }
        }
        return level;
    }

测试结果

    private TreeNode init(){
        TreeNode a = new TreeNode("A");
        TreeNode b = new TreeNode("B");
        TreeNode c = new TreeNode("C");
        TreeNode d = new TreeNode("D");
        TreeNode e = new TreeNode("E");
        TreeNode f = new TreeNode("F");
        TreeNode g = new TreeNode("G");
        TreeNode h = new TreeNode("H");
        TreeNode i = new TreeNode("I");
        TreeNode j = new TreeNode("J");
        TreeNode k = new TreeNode("K");

        a.left = b;
        a.right = c;

        b.left = d;
        b.right = e;

        d.left = h;
        d.right = i;

        e.right = j;

        c.left = f;
        c.right = g;

        f.right = k;

        return a;
    }

    public static void main(String[] args) {
        LevelLenth levelLenth = new LevelLenth();
        TreeNode root = Traverse.init();

        System.out.println(levelLenth.maxLengh(root));//
        System.out.println(levelLenth.maxLengh2(root));//4

        System.out.println(levelLenth.minLengh(root));//3
        System.out.println(levelLenth.minLengh2(root));//3
    }