algorithm - 在 BST 中，如何让左指针指向父节点，右指针指向右兄弟节点

Question

通过执行级别顺序遍历并相应地更改，可以使右指针指向右兄弟。但是，我不知道同时执行此操作的程序。有什么建议么？

Answer 1

只需执行 BFS 并记住级别和父级。以下是一个c ++代码

void BSTRightSibling(BSTNode *root)
{
    queue<BSTNode*> q;
    map<BSTNode*, BSTNode*> m;
    BSTNode* levelNode = root;

    q.push(root);
    while(! q.empty()) {
        BSTNode* n = q.front();
        if (n->left) {
            q.push(n->left);
            m[n->left] = n;
            if (n == levelNode) {
                levelNode = n->left;
            }
        }
        if (n->right) {
            q.push(n.right);
            m[n->right] = n;
            if (n == levelNode) {
                levelNode = n->right;
            }
        }
        q.pop();
        if ((!q.empty()) && (n != levelNode)) {
            n->right = q.front();
        } else {
            n->right = NULL;
        }
        n->left = m[n];
    }
}

Answer 2

在锦标赛问题中，您可以使用格雷码来决定它何时是左节点或右节点。另一种方法是，如果该值小于或等于父值，则其为右节点。