My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private class Result {
int size;
int min;
int max;
Result(int size, int min, int max) {
this.size = size;
this.min = min;
this.max = max;
}
}
private int maxNum = 0;
public int largestBSTSubtree(TreeNode root) {
if (root == null) {
return 0;
}
helper(root);
return maxNum;
}
private Result helper(TreeNode root) {
if (root == null) {
return new Result(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
Result left = helper(root.left);
Result right = helper(root.right);
if (left.size == -1 || right.size == -1 || root.val < left.max || root.val > right.min) {
return new Result(-1, 0, 0);
}
int size = left.size + 1 + right.size;
maxNum = Math.max(maxNum, size);
int min = (left.min == Integer.MAX_VALUE ? root.val : left.min);
int max = (right.max == Integer.MIN_VALUE ? root.val : right.max);
return new Result(size, min, max);
}
}
reference:
https://discuss.leetcode.com/topic/36995/share-my-o-n-java-code-with-brief-explanation-and-comments
这道题目并没能自己写出来。。。
类似的想法是有的。就是从底到顶，backtracking
当时我怎么想的呢？然后放弃了。
我想的是返回一个二维数组，第一位表示size，第二位表示这棵树最大值。
后来发现对于右子树来说，我们还需要知道最小值。然后我就懒得继续想下去了。
后来看了答案，发现返回一个类，类里面也是三个值：
size
min
max
其实当时自己的想法就差一点了。
时间复杂度是 O(n)
然后这种自定义类，返回一个类的做法，的确比我返回一个三位数组好多了。
另外，当root == null的时候，处理的办法也是亮点。
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
所以如果是左子树为空，那么我们需要看他的最大值是否小于root.val
的确是小于的，没问题。
如果右子树为空，那么我们需要看他的最小值是否大于root.val,
的确是大于的，没问题。
题目里说，如果是 top - down的recursion，时间复杂度是：
O(n log n) 一直没想明白。
Anyway, Good luck, Richardo! -- 09/07/2016
