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

ゝ一世哀愁。 2024-03-30 08:54 18阅读 0赞

## 需求： ##

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

上面这棵树的最大深度为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);
    	}
    }

**结果：**

[e8b60fb45f614436a06a6a62bf2b2002.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/13b88e9d1dc048b891702aafb93c3c45.png