LintCode 596 Minimum Subtree

思路

裸分治法。使用ResultType作为返回类型可以避免使用全局变量。

复杂度

时间复杂度O(n)
空间复杂度O(logn)

代码

/*** 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;* }* }*/
class ResultType {
    TreeNode minSubtree;int sum, minSum;ResultType(TreeNode minSubtree, int minSum, int sum) {
    this.minSubtree = minSubtree;this.sum = sum;this.minSum = minSum;}
}
public class Solution {
    /*** @param root: the root of binary tree* @return: the root of the minimum subtree*/public TreeNode findSubtree(TreeNode root) {
    // write your code hereResultType res = helper(root);return res.minSubtree;}private ResultType helper(TreeNode root) {
    if (root == null) {
    return new ResultType(null, Integer.MAX_VALUE, 0);}ResultType leftResult = helper(root.left);ResultType rightResult = helper(root.right);ResultType result = new ResultType(root,leftResult.sum + rightResult.sum + root.val, leftResult.sum + rightResult.sum + root.val);if (leftResult.minSum < result.minSum) {
    result.minSubtree = leftResult.minSubtree;result.minSum = leftResult.minSum;}if (rightResult.minSum < result.minSum) {
    result.minSubtree = rightResult.minSubtree;result.minSum = rightResult.minSum;}return result;}
}