题解 | #农场最大产奶牛群#

考察知识点： 深度优先搜索、后序遍历

题目分析：

 怎样找到一条路径，使得从一个任意节点到一个叶子节点之间的路径最短呢？我们先考虑简单的情况：

 当只有一个节点时，那么最大奶牛群就是这一个奶牛。当有上图所示的三个节点时，发现最大奶牛群是有根节点、左孩子和右孩子构成的。最大奶牛群中一定包含一个子树的根节点。当再复杂一些时，如下图所示：

 发现可以考虑以下问题：

1. 若把节点15看作根节点，节点35，15, 40可以构成最大产奶牛群吗？
2. 若把节点15看作路径中的某个点，那么从节点35过来的大还是从节点40过来的大？

 问题1只需要将左子树最长单向路径加上根节点的产奶量再加上右子树的最长单向路径，与现在得到的最大产奶牛群进行比较，维护这个最大值就可以了。而问题2也只需要比较左右子树中的最长单向路径即可。这时发现：计算上述两个问题需要首先知道左右节点中的最长单向路径。

 我需要先知道左右子树的信息，然后才能确定原子树的信息，这种遍历方式是后序遍历。我们让traverse函数返回一个最长的单向路径，在访问每个节点时计算以该节点为根节点时的奶牛群产量，并与最大奶牛群进行比较来维护最大值。

所用编程语言： 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 traverse(TreeNode *root, int &maxMilk) {
        if (!root) return 0;
        int left = traverse(root->left, maxMilk);
        int right = traverse(root->right, maxMilk);
        int path = left + right + root->val;
        maxMilk = max(maxMilk, path);
        return max(left, right) + root->val;
    }
    int maxMilkSum(TreeNode* root) {
        // write code here
        int maxMilk = 0;
        if (!root) return 0;
        traverse(root, maxMilk);
        return maxMilk;
    }
};