Time = O(n), space = O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int maxLen;
public int diameterOfBinaryTree(TreeNode root) {
maxLen = 1;
diameterOfBinaryTreeHelper(root);
return maxLen - 1;
}
public int diameterOfBinaryTreeHelper(TreeNode root) {
if (root == null) {
return 0;
}
int left = diameterOfBinaryTreeHelper(root.left);
int right = diameterOfBinaryTreeHelper(root.right);
int curMaxLen = left + right + 1;
maxLen = Math.max(maxLen, curMaxLen);
return Math.max(left, right) + 1;
}
}