333 Largest BST Subtree

333. Largest BST Subtree

1. Question

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?

2. Implementation

(1) Post-order Traversal

思路: 在后序遍历的过程中利用validate binary search tree的思想，对每个node的值，与它的leftSubTree最大值和rightSubtree最小值比较，如果node.val 小于等于leftSubTree的最大值或者大于等于rightSubTree的最小值，或者树的size是-1，则以该node作为root构成的树不是binary search tree. 然后每个node遍历完后返回一个数组，其中数组第一个元素存储的是以该node作为树的最小值，第二个元素存储的是以该node作为树最大值，第三个元素存储的是树的size。

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        int[] maxSize = new int[1];
        dfs(root, maxSize);
        return maxSize[0];
    }

    public long[] dfs(TreeNode node, int[] maxSize) {
        if (node == null) {
            return new long[] {Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }

        long[] left = dfs(node.left, maxSize);
        long[] right = dfs(node.right, maxSize);

        if (left[2] == -1 || right[2] == -1 || node.val <= left[1] || node.val >= right[0]) {
            return new long[] {0, 0, -1};
        }

        int count = (int)(left[2] + right[2] + 1);
        maxSize[0] = Math.max(maxSize[0], count);

        return new long[] {Math.min(left[0], node.val), Math.max(right[1], node.val), count};
    }
}

3. Time & Space Complexity

Post-order Traversal: 时间复杂度: O(n), 空间复杂度: O(h)