【力扣Hot100】543.二叉树的直径_力扣算法hot100

题目：二叉树的直径

分析：
还记不记得如何求二叉树的最大深度，那么如何求穿过根节点的直径，很显然答案就是将左子树的最大深度 + 右子树的最大深度；
但是题目中要求最大直径，也就是说最大直径路径不一定是穿过根节点的，所以要设置一个变量max，用来记录所有的子树的直径，然后更新最大值。

思路：

1. 设置一个全局变量max；
2. 对root进行求最大深度，调用下maxDeepth方法；
   • 越过叶子节点，返回0；
   • 计算左子树最大深度left；
   • 计算右子树最大深度right；
   • （在这个位置：计算直径 = left + right , 然后再维护最大值max）
   • 返回左右子树较大者 + 1；

代码：

class Solution {
    int sum = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        hepler(root);
        return sum;
    }

    private int hepler(TreeNode root) {

        if (root == null) {
            return 0;
        }
        int l = hepler(root.left);
        int r = hepler(root.right);
        sum = Math.max(sum, l + r);
        return Math.max(l, r) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18