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;
}

而 search_red(Node root) 是一个查找根下第一个 RED 节点的函数。如果你想在前序遍历中保持 RED 节点前后顺序相同，你的 search_red(Node root)是查找左 child 前序第一个节点，或者右 child 第一个节点。