数据结构篇之第（五）幕——树的深度（Java实现）

数据结构篇之第（五）幕——树的深度（Java实现）

main方法的开头，我先构造了一棵树，depth1()跟depth2()都是用了递归，depth3()借助了用queue实现的广度优先算法：

	
public class Depth {

    private static int maxDepth = 0;

    private static List depthAll = new ArrayList<>();

    public static void main(String[] args){
        BinaryTreeNode one = new BinaryTreeNode(10);

        BinaryTreeNode left = new BinaryTreeNode(5);
        left.setRight(new BinaryTreeNode(6));
        left.getRight().setRight(new BinaryTreeNode(8));
        one.setLeft(left);

        BinaryTreeNode right = new BinaryTreeNode(15);
        right.setLeft(new BinaryTreeNode(12));
        right.setRight(new BinaryTreeNode(18));
        one.setRight(right);

        depth1(one);
        int max = 0;
        for(int i = 0; i < depthAll.size(); i++){
            if(depthAll.get(i) > max){
                max = depthAll.get(i);
            }
        }
        System.out.println("depth1 result :" + max);
        System.out.println("depth2 result :" + depth2(one));
        System.out.println("depth3 result :" + depth3(one));
    }

    
    private static void depth1(BinaryTreeNode node){
        if(node == null){
            return;
        }
        maxDepth++;
        if(node.getLeft() != null || node.getRight() != null){
            depth1(node.getLeft());
            depth1(node.getRight());
        }else{
            System.out.println("leaf value: " + node.getValue());
            depthAll.add(maxDepth);
            maxDepth = 0;
        }
        return;
    }

    
    private static int depth2(BinaryTreeNode node){
        if(node == null){
            return 0;
        }
        return 1 + Math.max(depth2(node.getLeft()), depth2(node.getRight()));
    }

    
    private static int depth3(BinaryTreeNode node){
        Queue queue = new linkedList<>();
        queue.offer(node);
        BinaryTreeNode current;
        int level = 0;
        while(queue != null && queue.size() > 0){
            level++;
            int cur = 0;
            int last = queue.size();
            while(cur < last){
                current = queue.poll();
                if(current.getLeft() != null){
                    queue.offer(current.getLeft());
                }
                if(current.getRight() != null){
                    queue.offer(current.getRight());
                }
                cur++;
            }

        }
        return level;
    }
}

输出：

depth1 result :4
depth2 result :4
depth3 result :4