/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
Stack<TreeNode> S = new Stack<TreeNode>();//记录访问过的节点 Dictionary<TreeNode, List<TreeNode>> dic = new Dictionary<TreeNode, List<TreeNode>>(); private void postTree(TreeNode node)
{
if (node != null)
{
S.Push(node);
if (node.left != null)
{
postTree(node.left);
}
if (node.right != null)
{
postTree(node.right);
} if (node.left == null && node.right == null)
{
var nodelist = S.ToList();
nodelist.Reverse(); if (!dic.ContainsKey(node))
{
dic.Add(node, nodelist);
}
}
S.Pop();
}
} public int DiameterOfBinaryTree(TreeNode root)
{
postTree(root); var maxDiameter = ; foreach (var d in dic)
{
foreach (var d2 in dic)
{
if (d.Key == d2.Key)
{
var diameter = d2.Value.Count - ;
maxDiameter = Math.Max(maxDiameter, diameter);
}
else
{
//第一种情况：计算叶子节点到根节点的直径
var depth = d2.Value.Count - ; var c1 = d.Value.Count;
var c2 = d2.Value.Count;
var diameter = ; if (c1 < c2)
{
for (int i = ; i < c1; i++)
{
if (d.Value[i] != d2.Value[i])
{
diameter = c1 - i + c2 - i;
break;
}
}
}
else
{
for (int i = ; i < c2; i++)
{
if (d.Value[i] != d2.Value[i])
{
diameter = c1 - i + c2 - i;
break;
}
}
} //var IncCount = d.Value.Intersect<TreeNode>(d2.Value).Count();
//var diameter = (c1 - IncCount) + (c2 - IncCount); diameter = Math.Max(diameter, depth);
maxDiameter = Math.Max(maxDiameter, diameter);
}
}
}
return maxDiameter;
}
}
https://leetcode.com/problems/diameter-of-binary-tree/#/description
补充一种递归的方式，使用python实现：
思路是每次递归判断，以当前节点为根节点是否能达到最大，见第14行。
而每次递归向上返回的是当前节点的左右子树的高度的更大的一个，加上当前节点(+1)的高度，见第15行。
class Solution:
def __init__(self):
self.maxnum = #隐含的前提，最大的距离应该是两个叶子节点的距离
#本身这个函数是返回，当前节点到其所有叶子节点的最大深度
def getLength(self,root):
if root != None:
#左子树的最大深度
left = self.getLength(root.left)
#右子树的最大深度
right = self.getLength(root.right)
#在返回之前，更新maxnum
self.maxnum = max(self.maxnum,left+right)
return + max(left,right)
return def diameterOfBinaryTree(self, root: 'TreeNode') -> 'int':
self.getLength(root)
return self.maxnum
这道题目与leetcode104 二叉树的最大深度，思想是一样的，可以说是104题的升级版。