21 结点之和最小的子树（Minimum Subtree）

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.3 空间复杂度
  • 3 源码
  • • 3.1 遍历法

题目：结点之和最小的子树（Minimum Subtree）
描述：给一棵二叉树, 找到和为最小的子树, 返回其根节点。输入输出数据范围都在int内。

lintcode题号——596，难度——easy

样例1：

输入:{1,-5,2,1,2,-4,-5}
输出:1
解释：
这棵树如下所示：
     1
   /   
 -5     2
 /    /  
1   2 -4  -5 
整颗树的和-8是最小的，所以返回根节点1.

样例2：

输入:{1}
输出:1
解释:
这棵树如下所示：
   1
这棵树只有整体这一个子树，所以返回1.

  分治法和遍历法结合，使用分治法计算各个节点的和，使用遍历法计算和对比节点和的大小。

  需要完整遍历整棵树，算法的时间复杂度为O(n)。

  算法的空间复杂度为O(1)。

细节：

1. 需要在递归外定义minNode和minValue，向下传递时需要用引用方式&，特别注意TreeNode *指针传递的引用方式是TreeNode *&。

C++版本：

TreeNode* findSubtree(TreeNode *root) {
    // write your code here
    if (root == nullptr)
    {
        return root;
    }

    TreeNode *minNode = nullptr;
    int minValue = INT_MAX;
    calSum(root, minNode, minValue);
    return minNode;
}

int calSum(TreeNode *cur, TreeNode *&minNode, int &minValue)
{
    int sum = 0;
    if (cur == nullptr)
    {
        return sum;
    }

    int leftSum = calSum(cur->left, minNode, minValue);
    int rightSum = calSum(cur->right, minNode, minValue);
    
    sum = leftSum + rightSum + cur->val;

    if (sum < minValue)
    {
        minNode = cur;
        minValue = sum;
    }

    return sum;
}