Diameter of a Binary Tree

    和题 分析思路特别接近。

    2.     int val;
    3.     TreeNode left, right;
    4.     TreeNode(int val) {
    5.         this.val = val;
    6.         this.left = null;
    7.         this.right = null;
    8.     }
    9. }
    11. public class Solution {
    12.     public int diameter(TreeNode root) {
    14.         // left, right height
    16.         int rightHight = getHeight(root.right);
    18.         // left, right subtree diameter
    19.         int leftDia = diameter(root.left);
    20.         int rightDia = diameter(root.right);
    22.         int maxSubDia = Math.max(leftDia, rightDia);
    23.         return Math.max(maxSubDia, leftHight + 1 + rightHight);
    24.     }
    26.     private int getHeight(TreeNode root) {
    27.         if (root == null) return 0;
    29.         return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    31.     public static void main(String[] args) {
    32.         TreeNode root = new TreeNode(1);
    33.         root.left = new TreeNode(2);
    34.         root.right = new TreeNode(3);
    35.         root.left.left = new TreeNode(4);
    36.         root.left.right = new TreeNode(5);
    37.         root.left.right.left = new TreeNode(6);
    38.         root.left.right.left.right = new TreeNode(7);
    39.         root.left.left.left = new TreeNode(8);
    41.         Solution sol = new Solution();
    42.         int maxDistance = sol.diameter(root);
    43.         System.out.println("Max Distance: " + maxDistance);
    45. }