LeetCode Q333: Largest BST Subtree

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.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

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

Solution:

Use solution in Q98. Validate Binary Search Tree to solve this problem.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int helper(TreeNode* root, int& upperBound, int& lowerBound, int& maxNum){
	int res=0;
	if(root==NULL){
	upperBound=INT_MIN;
	lowerBound=INT_MAX;
	return res;
	}
	int lub, llb, rub, rlb;
	int lnum=helper(root->left, lub, llb, maxNum);
	int rnum=helper(root->right, rub, rlb, maxNum);
	lowerBound=root->left==NULL? root->val:llb;
	upperBound=root->right==NULL? root->val:rub;
	if(root->val>=lub&&root->val<=rlb&&lnum!=-1&&rnum!=-1){
	res=lnum+rnum+1;
	maxNum=max(res, maxNum);
	}else
	res=-1;
	return res;
	}
	int largestBSTSubtree(TreeNode* root) {
	int maxNum=0;
	if(root==NULL)
	return maxNum;
	int upperBound, lowerBound;
	helper(root, upperBound, lowerBound, maxNum);
	return maxNum;
	}
	};

view raw Q333.cpp hosted with ❤ by GitHub