每个级别的链接树节点

Question

给定二叉树,您将如何从左到右加入每个级别的节点.假设第3级有5个节点,从左到右连接所有节点.

我不需要任何人为此编写代码..但只是一个有效的算法.

谢谢

Answer 1

想法是:
1.使用BFS遍历树.
2.当您进行遍历时,您将链接下一级别的节点 - 如果节点具有左侧和右侧节点,则您将从左向右链接.如果节点有下一个节点,则将当前节点的最右边的子节点链接到下一个节点的最左边的子节点.

    public void BreadthFirstSearch(Action<Node> currentNodeAction)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        while (q.Count != 0)
        {
            Node current = q.Dequeue();

            if (currentNodeAction != null)
                currentNodeAction(current);

            if (current.left != null) q.Enqueue(current.left);
            if (current.right != null) q.Enqueue(current.right);
        }
    }

    private void Linker(Node node)
    {
        Link(node.left, node.right);

        if (node.next != null)
            Link(node.right ?? node.left, node.next.left ?? node.next.right);
    }

    private void Link(Node node1, Node node2)
    {
        if (node1 != null && node2 != null)
            node1.next = node2;
    }

    public void LinkSameLevel()
    {
        BreadthFirstSearch(Linker);
    }