Question:
Transform the binary search tree into a sorted two-way linked list.
do not use recursion.
do not create any new node, only adjust the pointer to point.
10
/ \
6 14
/ \ / \
4 8 12 16
-->>
4=6=8=10=12=14=16
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
Answer:
inline BSTreeNode* eleminateMinNode(BSTreeNode** tree) {
BSTreeNode* treeHead = tree;
if (!treeHead)
return 0;
BSTreeNode treeHeadParent = 0;
while (treeHead->m_pLeft) {
treeHeadParent = treeHead;
treeHead = treeHead->m_pLeft;
}
if (treeHeadParent)
treeHeadParent->m_pLeft = treeHead->m_pRight;
if (treeHead == *tree)
*tree = treeHead->m_pRight;
return treeHead;
}
inline BSTreeNode* eleminateMaxNode(BSTreeNode** tree) {
BSTreeNode* treeHead = tree;
if (!treeHead)
return 0;
BSTreeNode treeHeadParent = 0;
while (treeHead->m_pRight) {
treeHeadParent = treeHead;
treeHead = treeHead->m_pRight;
}
if (treeHeadParent)
treeHeadParent->m_pRight = treeHead->m_pLeft;
if (treeHead == *tree)
*tree = treeHead->m_pLeft;
return treeHead;
}
void BSTreeToDoubleLinkChainInternal(BSTreeNode* tree, BSTreeNode** headp, BSTreeNode** tailp) {
if (!tree)
return;
BSTreeNode* tail = tree;
BSTreeNode* right = tail->m_pRight;
BSTreeNode* minRight = eleminateMinNode(&right);
while (minRight && minRight != tail) {
tail->m_pRight = minRight;
minRight->m_pLeft = tail;
tail = minRight;
minRight = eleminateMinNode(&right);
}
tail->m_pRight = 0;
BSTreeNode* left = tree->m_pLeft;
BSTreeNode* maxLeft = eleminateMaxNode(&left);
BSTreeNode* head = tree;
while (maxLeft && maxLeft != head) {
head->m_pLeft = maxLeft;
maxLeft->m_pRight = head;
head = maxLeft;
maxLeft = eleminateMaxNode(&left);
}
head->m_pLeft = 0;
*headp = head;
*tailp = tail;
}
Subscribe to:
Post Comments (Atom)
fixed: embedded-redis: Unable to run on macOS Sonoma
Issue you might see below error while trying to run embedded-redis for your testing on your macOS after you upgrade to Sonoma. java.la...
-
Refer: https://github.com/bazelbuild/bazel/wiki/Building-with-a-custom-toolchain https://www.tensorflow.org/tutorials/image_recognition
-
Solution react-native bundle --platform android --dev false --entry-file index.js --bundle-output android/app/src/main/assets/index.android...
-
F:\webrowser>react-native run-android Scanning folders for symlinks in F:\webrowser\node_modules (73ms) Starting JS server... Buildin...
No comments:
Post a Comment