LeetCode543：二叉树的直径

要求

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

题目解析

这里返回的是：两结点之间的路径长度是以它们之间边的数目表示。
最大的直径不一定包括根节点，例：

思路

最大值不一定包含根节点，但经过一个节点，该节点等于左右子树的最大深度之和 +1
所以在计算深度的过程中，维护一个max全局变量，用来记录最大值，遍历完成后直接返回
使用 dfs(root) 遍历所有的节点，dfs(root) 的作用是：找出以 root 为根节点的二叉树的最大深度
root 为跟节点的最大深度为 Math.max(left,rigth) + 1
res 取值为已经过 root，左右子树的最大深度之和 left + rigth

public class LeetCode543 {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    //找到以root为根节点的二叉树最大深度
    private int dfs(TreeNode root) {
        if (root == null){
            return 0;
        }
        //递归到root节点的左子节点，最下方的，从下往上递归
        int left = dfs(root.left);
        int right = dfs(root.right);
        //获取当前节点的左右子树深度最大值
        res = Math.max(res, left + right);
        //+root节点
        return Math.max(left,right) + 1;
    }
}