c++ - 在伪二叉树中为每个 child 设置 sibling

Question

谁能告诉我使用递归的最简单的算法是什么，它会取一个所谓的二叉树的根(之所以这样称呼是因为严格来说它不是二叉树)并使这棵树中的每个 child 都与其 sibling 相连.
所以如果我有:

             1
           /   \  
          2     3  
         / \     \  
        4   5     6
       /           \
      7             8  

然后 2 的 sibling 将是 3、四五、五六和七八。

Answer 1

做一个BFS，给节点分配级别编号，并连接具有相同级别编号的节点。

伪代码:

void connectSiblings(Node root)
{
    Queue q = new Queue();
    root.level = 1;
    q.enqueue(root)
    while(!q.isEmpty())
    {
        elem = q.dequeue();
        //add elem's children to q
        if (elem.left != NULL)
        {
            elem.left.level = elem.level + 1;
            q.enqueue(elem.left);
        }
        if (elem.right != NULL)
        {
            elem.right.level = elem.level + 1;
            q.enqueue(elem.right);
        }

        //check level numbers and assign siblings
        if (elem.level == q.peek().level)
        {
             elem.sibling = q.peek();
             q.peek().sibling = elem;
        }
    }
}

peek() 函数给出队列中的下一个元素而不删除它。

我不确定你的问题到底是什么意思。但是，我希望这传达了这个想法。您可以调整它以满足您的需要。