2023年6月22日发(作者：)

【⼆叉树和分治算法】Lintcode596.最⼩⼦树Lintcode 596. 最⼩⼦树代码实现如下：/** * 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 */ //递归的定义 int findminSum(TreeNode * root, TreeNode*& minSubtree, int& minSum) { //递归的出⼝ if (nullptr == root) { return 0; } //递归的拆解 int leftSum = findminSum(root->left, minSubtree, minSum); int rightSum = findminSum(root->right, minSubtree, minSum); int tmpminSum = root->val + leftSum + rightSum; if (tmpminSum < minSum) { minSum = tmpminSum; minSubtree = root; }

return tmpminSum; }

TreeNode * findSubtree(TreeNode * root) { int minSum = INT_MAX; TreeNode* minSubtree = nullptr; //递归的调⽤ findminSum(root, minSubtree, minSum); return minSubtree; }};