算法- 求解最大平均值的子树-经典dfs题目

给一棵二叉树，找到有最大平均值的子树。返回子树的根结点。

Example

样例1

输入：
{1,-5,11,1,2,4,-2}
输出：11
说明:
这棵树如下所示：
     1
   /   \
 -5     11
 / \   /  \
1   2 4    -2 
11子树的平均值是4.333，为最大的。

样例2

输入：
{1,-5,11}
输出：11
说明:
     1
   /   \
 -5     11
1,-5,11 三棵子树的平均值分别是 2.333,-5,11。因此11才是最大的.
参考代码：

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the root of the maximum average of subtree
    """
    def findSubtree2(self, root):
        # write your code here
        self._result_node = None
        self._result_val = -float("inf")
        self.find_sub_tree(root)
        return self._result_node
    
    
    def find_sub_tree(self, root):
        if not root:
            return 0, 0
        
        left_sum, left_size = self.find_sub_tree(root.left)
        right_sum, right_size = self.find_sub_tree(root.right)
        
        sum = root.val + left_sum + right_sum
        size = left_size + right_size + 1
        avg_val = float(sum)/size
        
        if self._result_node is None or self._result_val < avg_val:
            self._result_node = root
            self._result_val = avg_val
            
        return sum, size

关于何时使用成员变量的问题，如果_result_node 不是成员变量，则需要以参数形式返回，在所有节点遍历时候用到，导致代码重复，因此直接使用成员变量（有点全局的味道）更好。

官方代码：【写得比我好，尤其是成员变量使用static】

class Solution:
    # @param {TreeNode} root the root of binary tree
    # @return {TreeNode} the root of the maximum average of subtree
    average, node = 0, None

    def findSubtree2(self, root):
        # Write your code here
        self.helper(root)
        return self.node

    def helper(self, root):
        if root is None:
            return 0, 0

        left_sum, left_size = self.helper(root.left)
        right_sum, right_size = self.helper(root.right)

        sum, size = left_sum + right_sum + root.val, \
                    left_size + right_size + 1

        if self.node is None or sum * 1.0 / size > self.average:
            self.node = root
            self.average = sum * 1.0 / size

        return sum, size

需要在遍历中记住上次遍历节点，根据上次的节点和当前节点进行比较而得到result的算法模板：

class Solution():
last_node = None
result = None
 
def run(self, root):
self.dfs(root)
return self.result
 
def dfs(self):
if last_node is None:
last_node = root
else:
do_sth(last_node, root)
 
dfs(root.left)
 
dfs(root.right)