使用指针连接二叉树中的所有兄弟节点

Question

问题：https://www.educative.io/m/connect-all-siblings

我试图通过创建一个虚拟节点来连接所有兄弟节点，并使用下一个指针将其设置在我们当前访问的节点旁边，但是在执行代码之后：

    public static void populate_sibling_pointers(BinaryTreeNode root) {
        if(root == null) return;
        Queue<BinaryTreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            int size = q.size();
            BinaryTreeNode dummy = new BinaryTreeNode(0);
            for(int i = 0; i < size; i++){
                BinaryTreeNode cur = q.poll();
                dummy.next = cur;
                dummy = dummy.next;
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }            
            }
        }
    }

我仍然没有通过一些测试，但我不确定我在这里做错了什么。感谢您的帮助！

Answer 1

两个问题：

您应该只创建一个 new 虚拟节点一次。通过在 while 循环的每次迭代中创建一个新的，您打破了 next 引用链。因此，该节点的创建应该发生在之前 while 循环。
next 链中的最后一个节点应将其 next 设置为 null。

这是更正后的代码：

class connectSiblings{
    public static void populate_sibling_pointers(BinaryTreeNode root) {
        if(root == null) return;
        Queue<BinaryTreeNode> q = new LinkedList<>();
        q.offer(root);

        BinaryTreeNode dummy = new BinaryTreeNode(0);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                BinaryTreeNode cur = q.poll();
                dummy.next = cur;
                dummy = dummy.next;
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }            
            }
        }
        dummy.next = null;
    }
}

您可以通过使用 next 引用将 LinkedList 的使用替换为您正在构建的实际链表来进一步优化此代码：当树的一层已正确连接时next引用，你可以迭代那个链表的那部分来找到并连接下一层的节点，然后它可以作为下一层的链表，......等等

使用指针连接二叉树中的所有兄弟节点

Connect All Siblings in Binary Tree Using Pointers

binary-tree

pointers

siblings