Leetcode

算法的核心思想是通过递归遍历整棵二叉树，在每个节点处计算它的左右子树的深度，并且利用这些深度来更新最大直径。详细解释如下：

算法思路：

1. 递归遍历每个节点：

   • 通过递归，从树的最底层（叶子节点）开始向上逐层计算每个节点的左右子树的深度。
   • 对于每个节点，递归函数depth()会先计算该节点的左子树深度和右子树深度。

2. 更新最大直径：

   • 对于每个节点，二叉树经过该节点的路径长度就是左子树的深度 + 右子树的深度。
   • maxDiameter变量用于记录当前的最大直径。如果当前节点的左右子树深度之和（即路径长度）大于已有的maxDiameter，就更新maxDiameter。

3. 返回节点的深度：

   • depth()函数返回当前节点的深度，这个深度是该节点到其最深叶子节点的距离，具体为：
     [
     \text{深度} = \max(\text{左子树深度}, \text{右子树深度}) + 1
     ]
   • 递归结束时，这个返回值会被用于父节点的递归调用，帮助父节点计算它的深度和直径。

关键点：

• 递归计算深度：每个节点的深度就是左右子树深度中的较大者加1，这个值递归地传递给上一级节点。
• 最大直径更新：直径是在递归过程中不断更新的，通过对每个节点计算它的左右子树深度之和，并与当前最大直径比较，实时更新。

最终结果：

当递归结束时，maxDiameter中保存的就是整个树的最大直径。

图解：

举例说明，假设我们有以下二叉树：

        1
       / \
      2   3
     / \
    4   5

1. 递归先从叶子节点4、5、3开始，计算它们的深度为1。
2. 节点2的左右子树深度分别为1（左）和1（右），所以节点2的深度为2，并且通过节点2的路径长度为1 + 1 = 2，此时更新直径为2。
3. 节点1的左右子树深度分别为2（左）和1（右），所以节点1的深度为3，通过节点1的路径长度为2 + 1 = 3，更新直径为3。

因此，最终直径为3。

这个算法的时间复杂度是O(N)，因为我们访问每个节点一次，计算它的深度和更新最大直径。

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    private int maxDiameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depthoftree(root);
        return maxDiameter;
    }
    private int depthoftree(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftsubtreedepth = depthoftree(root.left);
        int rightsubtreedepth = depthoftree(root.right);


        maxDiameter = Math.max(leftsubtreedepth + rightsubtreedepth, maxDiameter);
        
        return Math.max(leftsubtreedepth, rightsubtreedepth) + 1;
        
    }
}

原文地址：https://blog.csdn.net/coldasice342/article/details/143026784

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！