[leetcode]: 543. Diameter of Binary Tree

1.题目

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:
Given a binary tree

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.

翻译：给定一棵二叉树，求该树上两个节点之间最长距离

2.分析

例子中最长距离其实是左子树深度+右子树深度。
另一种情况是：

1
     /   \
    2     3
   /  \     
  4     5   
 /  \    / \
6    7   8  9
/ \        / \
11 12      13 14

最长距离出现在11-14
拓展到一般情况：最长距离为这棵树及其所有子树的最长距离的最大值。

3.代码

int diameterOfBinaryTree(TreeNode* root) {
    if (root == NULL)
        return 0;
    return max(getTreeHeight(root->left) + getTreeHeight(root->right), max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
int getTreeHeight(TreeNode* root) {
    if (root == NULL)
        return 0;
    return 1 + max(getTreeHeight(root->left), getTreeHeight(root->right));
}