Largest BST Subtree

https://leetcode.com/problems/largest-bst-subtree/description/

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:

A subtree must include all of its descendants.

Here's an example:

10

/ \

5 15

/ \

1 8 7

The Largest BST Subtree in this case is the highlighted one.

The return value is the subtree's size, which is 3.

Follow up:

Can you figure out ways to solve it with O(n) time complexity?

Thoughts

分治, 检查当前点是否满足BST条件, 即当左右子树都是BST时,node.val比左子树最大值大, 比右子树最小值小. 因此局部需要保存三个值, res[0]保存当前节点和子树构成bst时的size, 置为-1如果不能构成bst, res[1]保存能构成bst时整棵子树的最小值, res[2]保存子树最大值. 外加一个全局变量保存全局当前能构成的最大bst是多大.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = 0;
    private int[] helper(TreeNode root) {
        int[] res = new int[3]; // res, min, max
        if (root == null) {
            return res;
        }

        int[] left = helper(root.left);
        int[] right = helper(root.right);

        if (left[0] == -1 || right[0] == -1 || left[0] != 0 && root.val <= left[2] || right[0] != 0 && root.val >= right[1]) {
            res[0] = -1;
            return res;
        }

        res[0] = left[0] + right[0] + 1;
        max = Math.max(max, res[0]);
        res[1] = left[0] == 0 ? root.val : left[1];
        res[2] = right[0] == 0 ? root.val : right[2];

        return res;
    }

    public int largestBSTSubtree(TreeNode root) {
        helper(root);
        return max;
    }
}

Analysis

时间复杂度O(N).