[LeetCode]Diameter of Binary Tree

找二叉树直径的问题，等价于找无向无环图直径的问题，等价于找无向无环图最长路径的问题。递归的方法，很简单就不多说了。时间复杂度O(n)，代码如下：

	/**
	* 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) {
	int res = 0;
	recursion(root, res);
	return res? res - 1: 0;
	}
	private:
	int recursion(TreeNode* root, int& res)
	{
	if(!root)return 0;
	int left = recursion(root->left, res);
	int right = recursion(root->right, res);
	res = max(res, left + right + 1);
	return max(left, right) + 1;
	}
	};

view raw Diameter of Binary Tree.cpp hosted with ❤ by GitHub