# 543. Diameter of Binary Tree 二叉树的直径

@TOC

## # 题目描述

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.

## # 解题方法

### # 递归

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) {
if (!root) return 0;
distanceToLeaf(root);
return res - 1;
}
int distanceToLeaf(TreeNode* root) {
if (!root) return 0;
if (m.count(root)) return m[root];
int left = distanceToLeaf(root->left);
int right = distanceToLeaf(root->right);
res = max(left + right + 1, res);
int distance = max(left, right) + 1;
m[root] = distance;
return distance;
}
private:
int res = INT_MIN;
unordered_map<TreeNode*, int> m;
};
``````

Java代码如下：

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
DeepOfTree(root);
return max;
}
public int DeepOfTree(TreeNode root){
if(root == null) return 0;
int left = DeepOfTree(root.left);
int right = DeepOfTree(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
}
``````

Python代码如下：

``````# 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
"""
if not root:
return 0
self.diameter = 0
self.getDepth(root)
return self.diameter

def getDepth(self, root):
if not root:
return 0
left = self.getDepth(root.left)
right = self.getDepth(root.right)
self.diameter = max(self.diameter, left + right)
return 1 + max(left, right)
``````

124. Binary Tree Maximum Path Sumopen in new window

## # 日期

2017 年 4 月 21 日 2018 年 11 月 16 日 —— 又到周五了！ 2019 年 9 月 27 日 —— 昨天面快手，竟然是纯刷题