二叉树-二叉树的最大深度问题（4）-蒲公英云

二叉树-二叉树的最大深度问题（4）

需求：

给定一棵树，请计算树的最大深度（树的根节点到最远叶子结点的最长路径上的结点数）;
在这里插入图片描述

上面这棵树的最大深度为4。

实现:

API求最大深度：
public int maxDepth()：计算整个树的最大深度
private int maxDepth(Node x):计算指定树x的最大深度
实现步骤：
1.如果根结点为空，则最大深度为0；
2.计算左子树的最大深度；
3.计算右子树的最大深度；
4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
代码：

//计算整个树的最大深度
public int maxDepth() {
    return maxDepth(root);
}
//计算指定树x的最大深度
    private int maxDepth(Node x) {
    //1.如果根结点为空，则最大深度为0；
    if (x == null) {
    return 0;
}
    int max = 0;
    int maxL = 0;
    int maxR = 0;
    //2.计算左子树的最大深度；
    if (x.left != null) {
        maxL = maxDepth(x.left);
    }
    //3.计算右子树的最大深度；
    if (x.right != null) {
        maxR = maxDepth(x.right);
    }
    //4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
    max = maxL > maxR ? maxL + 1 : maxR + 1;
    return max;
}
//测试代码
public class Test {
public static void main(String[] args) throws Exception {
    BinaryTree<String, String> bt = new BinaryTree<>();
    bt.put("E", "5");
    bt.put("B", "2");
    bt.put("G", "7");
    bt.put("A", "1");
    bt.put("D", "4");
    bt.put("F", "6");
    bt.put("H", "8");
    bt.put("C", "3");
    int i = bt.maxDepth();
    System.out.println(i);
    }
}