n****t
发帖数: 241 | 1 我看到貌似正确的一个解法，加了很多限制条件。。。
面试题之二叉搜索树的中位数 收藏
这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
* No extra memory.
* Function should be reentrant (No static, global variables allowed.)
* Median for even no of nodes will be the average of 2 middle elements and
for odd no of terms will be middle element only.
* Algorithm should be efficient in terms of comple... 阅读全帖 |
|
|
发帖数: 1 | 3 Naïve Bayes
$$Pleft ( frac{A}{B} right ) = frac{Pleft ( frac{B}{A} right )Pleft ( A
right )}{Pleft ( B right )}$$ |
|
h*****f
发帖数: 248 | 4 #include
struct Node {
int value;
Node* pLeft;
Node* pRight;
};
int findMaxSubTree(Node* pNode, int& maxSoFar) {
if (!pNode) return 0;
int leftSum = findMaxSubTree(pNode->pLeft, maxSoFar);
int rightSum = findMaxSubTree(pNode->pRight, maxSoFar);
int currentSum = pNode->value + std::max(0, leftSum) + std::max(0,
rightSum);
maxSoFar = std::max(currentSum, maxSoFar);
return currentSum;
}
int main() {
Node node4 = {4, NULL, NULL};
Node node3 = {3, NULL, NULL... 阅读全帖 |
|
b***m
发帖数: 5987 | 5 我的这个code貌似跟二爷的意思一样？
int g_nMax = MIN_INT;
int MaxPathSum(Node *pNode)
{
if( !pNode ) return 0;
int nMaxLeft = MaxPathSum(pNode->pLeft);
int nMaxRight = MaxPathSum(pNode->pRight);
int nMaxCurrent = pNode->data + max(0, nMaxLeft) + max(0, nMaxRight);
g_nMax = max(g_nMax, nMaxCurrent);
int nMaxLeftRight = max(nMaxLeft, nMaxRight);
return nMaxLeftRight > 0 ? nMaxLeftRight + pNode->data : pNode->data;
} |
|
b***m
发帖数: 5987 | 6 我一般用这个：
void InOrder(Node *pRoot)
{
Stack s;
Node *pNode = pRoot;
while( pNode || !s.Empty() )
{
while( pNode )
{
s.push(pNode);
pNode = pNode->pLeft;
}
if( !s.Empty() )
{
pNode = s.pop();
Visit(pNode);
pNode = pNode->pRight;
}
}
} |
|
