Amazon : 寻找最大BST子结构大小

给一颗普通的二叉树，找出这棵树最大BST子结构的大小
(子结构懂不，不是子树是子结构！！！！！！！！！！！)

回复 1# wwwyhx
感觉跟上次那个差不多，也得再写个函数判断根节点为某个节点的最大BST子结构，然后搞各种情况

int _inner_get_max(TREE_NODE* pRoot, int& nLow, int& nHigh, int& nCurLargest)
{
        assert(NULL != pRoot);

        nLow = nHigh = pRoot->nVal;
        int nRet = 1;

        if (NULL != pRoot->pLft)
        {
                int nTmpLow, nTmpHigh;
                int nSize = _inner_get_max(pRoot->pLft, nTmpLow, nTmpHigh, nCurLargest);

                if (pRoot->nVal >= nTmpHigh)
                {
                        nRet += nSize;
                        nLow = nTmpLow;
                }
        }

        if (NULL != pRoot->pRgt)
        {
                int nTmpLow, nTmpHigh;
                int nSize = _inner_get_max(pRoot->pRgt, nTmpLow, nTmpHigh, nCurLargest);

                if (pRoot->nVal <= nTmpLow)
                {
                        nRet += nSize;
                        nHigh = nTmpHigh;
                }
        }

        if (nRet > nCurLargest) nCurLargest = nRet;

        return nRet;
}

int GetMaxBSTSize(TREE_NODE* pRoot)
{
        if (NULL == pRoot) return NULL;

        int nCurLargest = 1;
        int nLow, nHigh;

        _inner_get_max(pRoot, nLow, nHigh, nCurLargest);

        return nCurLargest;
}