LindCode

Minimum Subtree.txt

/**
 * 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 int sum = Integer.MAX_VALUE;
     private TreeNode subnode = null;
    public TreeNode findSubtree(TreeNode root) {
        //找Minimum Subtree，一是需要每个节点的subtree sum，二是将每个节点的subtree sum进行比较，找出最小的
        //每个节点的subtree sum traverse或者divide conquer都可以，找最小的sum就打擂台算法
        //用helper函数
        helper(root);
        return subnode;
    }
    private int helper(TreeNode curnode){
        //设置出口,如果当前节点为空则退出
        if(curnode == null){
            return 0;
        }
        //当前节点的sum等于左子树的sum+右子树的sum+当前节点的值
        int cursum = helper(curnode.left) + helper(curnode.right) + curnode.val;
        //打擂台算法，当前节点的sum和全局sum相比较，将全局sum设置为正无穷大，
        //如果当前节点的sum小于全局变量sum，将当前节点和当前节点sum赋值给全局变量
        if(cursum<sum){
            sum = cursum;
            subnode = curnode;
            
        }
        
        return cursum;
    }
}

/**
 * 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
     */
    class ResultType{
        TreeNode node;
        int sum;
        public ResultType(TreeNode node, int sum){
            this.node = node;
            this.sum = sum;
        }
    }
    ResultType result = null;
    
    public TreeNode findSubtree(TreeNode root) {
        /**用divide conquer，设置
         * result type，resulttype中包含想要返回的值的类型，
         * 就本题而言，需要返回一是sum，一个是当节点
         * 思路这一类的题目都可以这样做：
         * 开一个ResultType的变量result，来储存拥有最小sum的那个node的信息。
         * 然后用分治法来遍历整棵树。
         * 一个小弟找左子数的sum，一个小弟找右子树的sum.
         * 同时，我们根据算出来的当前树的sum决定要不要更新result。
         当遍历完整棵树的时候，result里记录的就是拥有最小sum的子树的信息。*/
        //设置异常
        if(root == null){
            return null;
        }
        helper(root);
        return result.node;
    }
    private ResultType helper(TreeNode node){
        if(node == null){
            return new ResultType(null,0);
        }
        ResultType left = helper(node.left);
        ResultType right = helper(node.right);
        ResultType currResult = new ResultType(node, 
                left.sum + right.sum + node.val);
        if( result == null ||currResult.sum < result.sum ){
            result = currResult;
        }
        return currResult;
    }
    
}