Lintcode 596. Minimum Subtree

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

Example

Example 1:

Input:
{1,-5,2,1,2,-4,-5}
Output:1
Explanation:
The tree is look like this:
     1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5 
The sum of whole tree is minimum, so return the root.

Example 2:

Input:
{1}
Output:1
Explanation:
The tree is look like this:
   1
There is one and only one subtree in the tree. So we return 1.

Notice

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.

Code (Java):

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    private TreeNode minNode = null;
    private int minSum = Integer.MAX_VALUE;
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        if (root == null) {
            return null;
        }
        
        findSubtreeHelper(root);
        
        return minNode;
    }
    
    private int findSubtreeHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = findSubtreeHelper(root.left);
        int right = findSubtreeHelper(root.right);
        
        int ret = root.val + left + right;
        
        if (ret < minSum) {
            minSum = ret;
            minNode = root;
        }
        
        return ret;
    }
}

Pure Divide and Conquer with ResultType

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        if (root == null) {
            return null;
        }
        
        ResultType ans = findSubtreeHelper(root);
        
        return ans.minNode;
    }
    
    private ResultType findSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, Integer.MAX_VALUE, null);
        }
        
        ResultType left = findSubtreeHelper(root.left);
        ResultType right = findSubtreeHelper(root.right);
        
        ResultType ans = new ResultType(root.val + left.sum + right.sum, 
                                        root.val + left.sum + right.sum,
                                        root);
        
        if (left.minSum < ans.minSum) {
            ans.minSum = left.minSum;
            ans.minNode = left.minNode;
        }
        
        if (right.minSum < ans.minSum) {
            ans.minSum = right.minSum;
            ans.minNode = right.minNode;
        }
        
        return ans;
        
    }
}

class ResultType {
    int sum;
    int minSum;
    TreeNode minNode;
    
    public ResultType(int sum, int minSum, TreeNode minNode) {
        this.sum = sum;
        this.minSum = minSum;
        this.minNode = minNode;
    }
}