最小/大子树

一、描述
给一棵二叉树, 找到和为最小的子树, 返回其根节点。
LintCode会打印根节点为你返回节点的子树。保证只有一棵和最小的子树并且给出的二叉树不是一棵空树。
您在真实的面试中是否遇到过这个题？ 是
题目纠错
样例
给一棵二叉树：

 1

/
-5 2
/ \ /
0 2 -4 -5
返回节点 1
题目链接：https://www.lintcode.com/problem/minimum-subtree/
1、通过全局变量来实现

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    TreeNode * findSubtree(TreeNode * root) {
        // write your code here
        if (root == NULL) {
            return NULL;
        }
        
        sumTree(root);
        
        return m_subRoot;
    }
    
    int sumTree(TreeNode * root) {
        if (root == NULL) {
            return 0;
        }
        
        int leftSum = sumTree(root->left);
        int rightSum = sumTree(root->right);
        
        int sum = leftSum + rightSum + root->val;
        
        if (sum <= m_subSum) {
            m_subSum = sum;
            m_subRoot = root;
        }
        return sum;
    }
    
private:
    TreeNode *m_subRoot = NULL;
    int m_subSum = INT_MAX; 
};

同理最大子树

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of binary tree
     * @return: the maximum weight node
     */
    TreeNode * findSubtree(TreeNode * root) {
        // write your code here
        if (root == NULL) {
            return NULL;
        }
        
        sumTree(root);
        
        return m_subRoot;
    }
    
    int sumTree(TreeNode * root) {
        if (root == NULL) {
            return 0;
        }
        
        int leftSum = sumTree(root->left);
        int rightSum = sumTree(root->right);
        
        int sum = leftSum + rightSum + root->val;
        
        if (sum >= m_subSum) {
            m_subSum = sum;
            m_subRoot = root;
        }
        return sum;
    }
    
private:
    TreeNode *m_subRoot = NULL;
    int m_subSum = INT_MIN; 
};

二、具有最大平均数的子树
描述
给一棵二叉树，找到有最大平均值的子树。返回子树的根结点。
LintCode会打印出根结点为你返回节点的子树，保证有最大平均数子树只有一棵
您在真实的面试中是否遇到过这个题？ 是
题目纠错
样例
给一个二叉树：

 1

/
-5 11
/ \ /
1 2 4 -2
返回节点 11。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
struct ResultType {
public:
     int sum;
     int size;
     ResultType() : sum(0), size(0) {}
     ResultType(int _sum, int _size) : sum(_sum), size(_size) {}
};

class Solution {
public:
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    TreeNode * findSubtree2(TreeNode * root) {
        // write your code here
        if (root == NULL) {
            return NULL;
        }
        
        sumTree(root);
        
        return m_subRoot;
    }
    
    ResultType sumTree(TreeNode * root) {
        ResultType result;
        if (root == NULL) {         
            return result;
        }

        ResultType resultLeft = sumTree(root->left);
        ResultType resultRight = sumTree(root->right);
        
        result.sum = resultLeft.sum + resultRight.sum + root->val;
        result.size = resultLeft.size + resultRight.size + 1;
        
        if (m_subRoot == NULL || result.sum * m_subResult.size >= m_subResult.sum * result.size) {
            m_subRoot = root;
            m_subResult = result;
        }
        return result;
    }
    
private:
    TreeNode *m_subRoot = NULL;
    ResultType m_subResult; 
};

以上还可以通过分治法实现，详细见链接：
https://www.jianshu.com/p/af2af240ac5f