Leetcode 333 Solution

This article provides solution to leetcode question 333 (largest-bst-subtree)

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

Solution

/** * 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 { int res = 0;
public: bool largestBSTSubtree(TreeNode* root, int& min_val, int& max_val, int& size) { if (root == NULL) { size = 0; max_val = INT_MIN; min_val = INT_MAX; return true; }
int left_size, left_min, left_max; bool left_bst = largestBSTSubtree(root->left, left_min, left_max, left_size);
int right_size, right_min, right_max; bool right_bst = largestBSTSubtree(root->right, right_min, right_max, right_size);
size = 1 + left_size + right_size;
bool valid = (left_max < root->val && root->val < right_min) && left_bst && right_bst;
if (valid) res = max(size, res);
min_val = root->val; min_val = min(min_val, left_min); min_val = min(min_val, right_min);
max_val = root->val; max_val = max(root->val, left_max); max_val = max(root->val, right_max);
return valid; }
int largestBSTSubtree(TreeNode* root) { int size = 0; int min_val, max_val; largestBSTSubtree(root, min_val, max_val, size); return res; } };