2025年- H46-Lc154 --543. 二叉树的直径(深度、递归、深搜）--Java版

1.题目描述

2.思路

径定义为“路径经过的节点数 - 1”，而递归中我们实际是在统计“边数”。
left + right 就已经是边数，无需再减 1。
Depth() 返回的是深度（从当前节点到底部的边数），而不是节点数。如果你返回节点数，就要额外处理 -1。

3.代码实现

 class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}public class H543 {int diameter;//定义一个类的成员变量，也就是全局变量。这个值可以实时更新迭代。用来存储当前遍历到的最大直径值。public int diameterOfBinaryTree(TreeNode root) {diameter=0;Depth(root);//传入二叉树的节点值，计算每个节点的深度，同时更新最大直径return diameter;}private int Depth(TreeNode root){if(root==null)return 0;int left=Depth(root.left);//递归计算当前节点左子树和右子树的最大深度。int right=Depth(root.right);//两者之和就是经过该节点的路径长度。diameter=Math.max(diameter,left+right);//更新全局最大直径值：当前最大值和 left + right 中取最大值。径定义为“路径经过的节点数 - 1”，而递归中我们实际是在统计“边数”。return 1+Math.max(left,right);//当前节点的深度 = 左右子树最大深度 + 1（算上当前节点）。返回给上一层节点使用。
//left + right 就已经是边数，无需再减 1。}public static void main(String[] args){H543 test=new H543();TreeNode node3=new TreeNode(3,null,null);TreeNode node2=new TreeNode(2,null,null);TreeNode head =new TreeNode(1,node2,node3);int res=test.diameterOfBinaryTree(head);System.out.print(res);}}