algorithm - 从树中删除所有蓝色节点

Question

给定一棵二叉树，其节点具有颜色属性。树有红色节点和蓝色节点。

从树中删除所有蓝色节点并返回只有红色节点的树？

我试图这样实现：

Node stripblue(Node root)
{
    if(root.left != NULL)
      root.left = stripblue(root.left) //is this line correct ? //TODO

    if(root.right != NULL)
       root.right = stripblue(root.right) // is this line correct ? //TODO

     if(root.color == RED)
     return root
}

我在实现TODO我的算法部分时遇到了一些麻烦。有人可以给我一些想法吗？

Answer 1

如果对删除前后的遍历顺序没有限制，我就写一个，看起来像是普通二叉树节点的删除。

Node stripblue(Node root)
{
    if(root == NULL)
        return NULL;
    if(root.color == BLUE)
    {
        Node next_r;
        next_r = search_red(root.left);
        if(next_r == NULL)
            next_r = search_red(root.right);
                if(next_r == NULL)
                    return NULL;
                    //no node is RED

            //TODO:swap the content of next_r and root
            next_r.color = BLUE;
            root.color = RED;
    }
    root.left  = stripblue(root.left);
    root.right = stripblue(root.right);
    return root;
}

whilesearch_red(Node root)是查找根下第一个 RED 节点的函数。如果要在前序遍历中保持 RED 节点的顺序前后相同，则要search_red(Node root)找到左子节点的前序中的第一个节点，或者右孩子的第一个节点。