Minimum subtree

我一開始是寫這樣：

int min = Integer.MAX_VALUE;

public TreeNode findSubtree(TreeNode root) {
    if (root == null) {
        return null;
    }    

    helper(root);
    return minNode;
}

public void helper(TreeNode root) {
    if (root == null) {
        return;
    }

    if (root.val + min < min) {
        min = root.val + min;
        minNode = root;
    }

    helper(root.left);
    helper(root.right);
    return;
}

可以發現問題出在於我根本沒有比較 root + left + right 這樣的值

所以在 {1,-1,2,1,2,-4,-5} 這種測資會過不了，

改良後是這樣

TreeNode minNode = null;
int min = Integer.MAX_VALUE;

public TreeNode findSubtree(TreeNode root) {
    if (root == null) {
        return null;
    }    

    helper(root);
    return minNode;
}

public int helper(TreeNode root) {
    if (root == null) {
        return 0;
    }

    //先將 subtree 加起來再遞迴求解！！
    int subtreeSum = helper(root.left) + helper(root.right) + root.val;
    if (subtreeSum < min) {
        min = subtreeSum;
        minNode = root;
    }
    return subtreeSum;
}

這樣做完用 divide & conquer 也會了，就是核心的比較要寫出來

divide & conquer:

用 divide & conquer 需要 Result 的輔助，因為必須要將每次的結果回傳才能比較