首页 > itarticle > lint596. minimum subtree

lint596. minimum subtree

admin 11月 14, 2020 0

Description

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

Example

Example 1:

Input:
     1
   /   
 -5     2
 /    /  
0   2 -4  -5

Output:1

Example 2:

1
2

Input:
   1

Output:1

> Solve problem here

Thoughts

Since it is a tree type problem, we can use BFS or DFS to solve it. Since it is looking for sum of subtree, hence, DFS is more appropriated. Lets use divide and conquer approch and recursive dfs to solve it first.

DFS recurisve + divide and conquer (w/ global vars, traverse)

Note: traverse is because we are using global var (拿着笔记本走整颗树记录最小值)


 * 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  {
    
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
     
    private int minSum;
    private TreeNode;
    
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        minSum = Integer.MAX_VALUE;
        minRoot = root;
        // divide n conquer
        getSum(root);
        
        return minRoot;
    }
    
    public int getSum(TreeNode node) {
        if (node == null) return 0;
        
        int left = getSum(node.left);
        int right = getSum(node.right);
        int sum = left + right + node.val;
        
        if ( sum < minSum ) {
            minSum = sum;
            minRoot = node;
        }
        
        return sum;
    }
}

The above solution is not pure divide and conquer since it uses global variable. To make it pure divide and conquer, we can wrap global variables into a wrapper ResultType

DFS recursive + pure divide and conquer

public class  {
    
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    private class ResultType {
        private int sum;
        private TreeNode node;
        public ResultType(int sum, TreeNode node) {
            this.sum = sum;
            this.node = node;
        }
    }

    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        // divide n conquer
        ResultType res = new ResultType(Integer.MAX_VALUE, root);
        getSum(root, res);
        return res.node;
    }
    
    public int getSum(TreeNode node, ResultType min) {
        if (node == null) return 0;
        
        int left = getSum(node.left, min);
        int right = getSum(node.right, min);
        int sum = left + right + node.val;
        
        if ( sum < min.sum ) {
            min.sum = sum;
            min.node = node;
        }
        
        return sum;
    }
}

Summary

divide and conquer (wo/ global vars 大王派小弟) VS traversal (w/ global vars 带着笔记本)

Logs

02/05/2019: add solutions

Reference