Java实现 LeetCode 543. 二叉树的直径（遍历树）-蒲公英云

Java实现 LeetCode 543. 二叉树的直径（遍历树）

543. 二叉树的直径

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

示例 :
给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。
PS：
二叉树的直径不一定过根节点，因此需要去搜一遍所有子树(例如以root，root.left, root.right…为根节点的树)对应的直径，取最大值。
root的直径 = root左子树高度 + root右子树高度
root的高度 = max {root左子树高度, root右子树高度} + 1

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution { 
     private int max = 0;
    public int diameterOfBinaryTree(TreeNode root) { 
        dfs(root);
        return max;
    }
    private int dfs(TreeNode root) { 
        if (root == null) { 
            return 0;
        }
        int leftHeight = dfs(root.left), rightHeight = dfs(root.right);
        max = Math.max(leftHeight + rightHeight, max);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}