543 Diameter of Binary Tree

Given a binary tree, you need to compute 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.

Example：

      1
     / \
    2   3
   / \     
  4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note：

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

解释下题目：

找到一棵树里的最长路径，该路径可能不经过根节点

1. 递归

实际耗时：0ms

int globalMax = 0;

public int diameterOfBinaryTree(TreeNode root) {
    helper(root);
    return globalMax;
}

private int helper(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        int left = helper(root.left);
        int right = helper(root.right);
        globalMax = Math.max(globalMax, left + right);
        return Math.max(left, right) + 1;
    }
}

  思路其实跟寻找最深子树是一样的，只不过多了一个全局变量用来记录一下最长的距离而已。

时间复杂度O(n) n为节点数，因为每个节点我们只访问了一次。

空间复杂度O(n) n为节点数，因为每个节点我们只访问了一次。