题解 | #牛群的最长距离#

考察知识点： 树的后序遍历

题目分析：

 我们可以首先缩小问题的规模，当只有一个节点时，路径长为0；当只有两个节点时，路径长为1。当有三个节点时，路径长为3。

 当有5个节点时，发现问题开始变得复杂起来。我们最终的选择是走4 2 1 3或5 2 1 3。我们为什么这样选？因为我们知道在这棵以1为根节点的树中，左子树中的最长路径为2,右子树中的最长路径为1。如果我们能提前知道左子树和右子树中的最长单向路径就好了。

 我们发现通过后序遍历的方式，能够让我们先访问左子树和右子树，最后再访问根节点。我们可以通过后序遍历记录左子树和右子树中的最长单向距离。在遍历时查看以该节点为根节点时，若加上左右子树的最长路径是否是比之前计算的最长路径更长的路径即可。

所用编程语言： C++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    int postOrder(TreeNode *root, int &res) {
        if (!root) return 0; 
        int left = postOrder(root->left, res);
        int right = postOrder(root->right, res);
        res = max(res, left + right);
        return 1 + max(left, right);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        // write code here
        if (!root) return 0;
        int res = 0;
        postOrder(root, res);
        return res;
    }
};