## Description

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

Example

Example 1:

Output:1

Example 2:

Output:1

## 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 (拿着笔记本走整颗树记录最小值)

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

## Summary

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