543. Diameter of Binary Tree
对于任意节点node,可以计算其左子树的深度left和右子树的深度right,left+right+1即为过node的最长距离。遍历树的节点,取最大值即可:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int ans=1;
public int diameterOfBinaryTree(TreeNode root) {
// if(root==null){
// return 0;
// }
helper(root);
return ans-1;
}
public int helper(TreeNode node){ //获取树的深度
if(node==null){
return 0;
}
int left = helper(node.left);
int right = helper(node.right);
ans = Math.max(ans,left+right+1);
return Math.max(left,right)+1;
}
}