【二叉树和分治算法】Lintcode 596. 最小子树

Lintcode 596. 最小子树

题目链接：https://www.lintcode.com/problem/minimum-subtree/description
描述：给一棵二叉树, 找到和为最小的子树, 返回其根节点。输入输出数据范围都在int内。

代码实现使用了遍历的方法。也想过分治算法，但感觉这道题更适合遍历的方法，个人觉得因为要对每棵子树进行遍历且要找和最小的，这里需要一个全局的变量记住最小和，以便遍历找到的每个子树和它进行比较，以此求最小子树，所以我觉得重新定义一个辅助函数，且借助全局变量的遍历方式进行递归也许会好一些。
代码中需要注意的地方是：int findminSum(TreeNode * root, TreeNode*& minSubtree, int& minSum) { ... }这个辅助递归函数中minSubtree变量，要是指向指针的指针，这里只是用了指针引用，道理是一样的。为什么需要这样？因为这个minSubtree指针在该函数中使用时，实际是为了存储root这个指针变量，而她本身又得是TreeNode指针，所以是为了记忆指针变量的指针，这里如果你只是使用TreeNode* minSubtree的话，最终返回的结果会是空。

代码实现如下：

/**
 * 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45