LeetCode # 543 二叉树中两节点的最长路径

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

示例 :
给定二叉树

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

解题思路：由题可知，两个节点之间路径长度的最大值一定会出现在某个节点左右子树高度之和，所以采用递归的方法，分别计算每个节点左右子树高度之和，找出最大值，返回。

class Solution {
    private int length = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return length;
    }
    private int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int depthLeft = maxDepth(root.left);
        int depthRight = maxDepth(root.right);
        if(length < (depthLeft+depthRight)){
            length = depthRight+depthLeft;
        }
        return Math.max(depthLeft,depthRight)+1;
    }
}