2014
01-10

# 面试题精选100题(11)－求二元查找树的镜像[数据结构]

8
/  \
6      10
/\       /\
5  7    9   11

8
/  \
10    6
/\      /\
11  9  7  5

struct BSTreeNode // a node in the binary search tree (BST)
{
int          m_nValue; // value of node
BSTreeNode  *m_pLeft;  // left child of node
BSTreeNode  *m_pRight; // right child of node
};

8
/  \
10    6
/\      /\
9  11  5  7

8
/  \
10    6
/\      /\
11  9  7   5

///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) recursively
// the head of BST in initial call
///////////////////////////////////////////////////////////////////////
void MirrorRecursively(BSTreeNode *pNode)
{
if(!pNode)
return;

// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;

// mirror left child sub-tree if not null
if(pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);

// mirror right child sub-tree if not null
if(pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}

///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) Iteratively
///////////////////////////////////////////////////////////////////////
{
return;

std::stack<BSTreeNode *> stackTreeNode;

while(stackTreeNode.size())
{
BSTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();

// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;

// push left child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);

// push right child sub-tree into stack if not null
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）