题目描述

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 
          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.

解法一

思路

二叉树上的任一“路径”上一定有一个结点是所有其他结点的祖先结点（因为“路径”是由一个个父子关系连接而成的），那么换个表述方法，对于任一结点，以此结点为根的diameter就可以表示为左子树高度 + 右子树高度 + 1，而二叉树的diameter就是所有结点为根的diameter中最大的那个。

那么这题实际也是一个二叉树遍历的问题，即对每个结点，计算左子树高度 + 右子树高度 + 1。那么应该用前序遍历还是后序遍历呢？如果我们把这题再抽象，其实就是一个求二叉树高度的问题，那么显然就是后序遍历了。

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.result = -1

        def diameter(root):
            if root is None:
                return 0
            left = diameter(root.left)
            right = diameter(root.right)
            length = left + right + 1
            self.result = max(self.result, length)
            return max(left, right) + 1

        diameter(root)

        return 0 if self.result == -1 else self.result - 1

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        class Utils {
            int result = -1;

            int diameter(TreeNode root) {
                if (root == null) {
                    return 0;
                }
                int left = diameter(root.left);
                int right = diameter(root.right);
                int length = left + right + 1;
                result = Math.max(result, length);
                return Math.max(left, right) + 1;
            }
        }
        Utils utils = new Utils();
        utils.diameter(root);
        return utils.result == -1 ? 0 : utils.result - 1;
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode *root) {
        class Utils {
        public:
            int result = -1;

            int diameter(TreeNode *root) {
                if (root == nullptr) {
                    return 0;
                }
                int left = diameter(root->left);
                int right = diameter(root->right);
                int length = left + right + 1;
                result = max(result, length);
                return max(left, right) + 1;
            }
        };
        Utils utils;
        utils.diameter(root);
        return utils.result == -1 ? 0 : utils.result - 1;
    }
};