543 Diameter of Binary Tree

LeetCode

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5] Output: 3 Explanation: 3is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2] Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104]. -100 <= Node.val <= 100

---

最大的距离为某个节点的左子树深度加上右子树深度

class Solution {
    int max=0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }
    
    private int depth(TreeNode t){
        if(t==null) return 0;
        int left=depth(t.left);
        int right=depth(t.right);
        max=max>left+right?max:left+right;
        return Math.max(left,right)+1;
    }
}