Lint596. Minimum Subtree

Description

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

Example

Example 1:

1
2
3
4
5
6
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 (拿着笔记本走整颗树记录最小值)

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
46
/**
* 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 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

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
public class Solution {
/**
* @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