Thinking process I - Traversal + Divide and Conquer
two global variables
helper function return current sum
Mistakes
In the helper function, the end condition should be when (root == null), otherwise the leaf node is not considered
public class Solution {
/**
* @param root the root of binary tree
* @return the root of the minimum subtree
*/
private TreeNode minSumRoot;
private int minSum;
public TreeNode findSubtree(TreeNode root) {
minSum = Integer.MAX_VALUE;
dfsHelper(root);
return minSumRoot;
}
private int dfsHelper(TreeNode root) {
if (root == null) {
return 0;
}
int currSum = dfsHelper(root.left) + dfsHelper(root.right) + root.val;
if (currSum < minSum) {
minSumRoot = root;
minSum = currSum;
}
return currSum;
}
}