文章目录
-
- 1 题目
- 2 解决方案
-
- 2.1 思路
- 2.2 时间复杂度
- 2.3 空间复杂度
- 3 源码
-
- 3.1 遍历法
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.
2 解决方案
2.1 思路
??分治法和遍历法结合，使用分治法计算各个节点的和，使用遍历法计算和对比节点和的大小。
2.2 时间复杂度
??需要完整遍历整棵树，算法的时间复杂度为O(n)。
2.3 空间复杂度
??算法的空间复杂度为O(1)。
3 源码
3.1 遍历法
细节：
- 需要在递归外定义minNode和minValue，向下传递时需要用引用方式
&，特别注意TreeNode *指针传递的引用方式是TreeNode *&。
C++版本：
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
/**
* @param root: the root of binary tree
* @return: the root of the minimum subtree
*/
TreeNode* findSubtree(TreeNode *root) {// write your code hereif (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;
}