C++ solution, using same method as validate binary search tree


  • 1
    M
    /**
     * 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 largestBSTSubtree(TreeNode* root) {
            if(!root)
                return 0;
            bool result = helper(root);
            if(result){
                int result = countnodes(root);
                return result;
            }
            else{
                int n1 = largestBSTSubtree(root->left);
                int n2 = largestBSTSubtree(root->right);
                return max(n1,n2);
            }
        }
        bool helper(TreeNode* root){
            stack<TreeNode*> s;
            TreeNode* wrongnode = NULL;
            TreeNode* current = root;
            while(1){
                while(current){
                    s.push(current);
                    current = current->left;
                }
                if(s.empty())
                    break;
                TreeNode* node = s.top();
                s.pop();
                if(wrongnode == NULL){
                    wrongnode = node;
                }
                else{
                    if(wrongnode->val >= node->val)
                        return false;
                    else
                        wrongnode = node;
                }
                current = node->right;
            }
            return true;
        }
        int countnodes(TreeNode* root){
            if(!root)
                return 0;
            return 1+countnodes(root->left)+countnodes(root->right);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.