java - 在左子右兄弟树中查找第一个元素

Question

在最近的一次采访中，我被问到这个问题。给定一个左子右兄弟树，找到树中第一个拥有真值的节点。（首先定义为最高级别，答案可以用 C++ 或 Java 实现

我的答案在下面，我相信它基于我迄今为止运行的测试用例。我想知道是否有更优雅的解决方案。我现在使用 3 个队列，这似乎不是最优的。

private class Node{
    Node child;
    Node sibling;
    boolean data;
}

Node findFirstTrue(Node n)
   {
    if (n == null)
    {
        return null;
    }
    if (n.data == true)
    {
        return n;
    }
    Queue<Node> searchNextSibling = new ArrayDeque<Node>();
    Queue<Node> searchNextChildren = new ArrayDeque<Node>();
    searchNextSibling.add(n);
    while(!searchNextSibling.isEmpty() || !searchNextChildren.isEmpty())
    {
        while(!searchNextSibling.isEmpty())
        {
            Node current = (test.Node) searchNextSibling.remove();
            if (current.data == true)
            {
                return current;
            }
            if (current.sibling != null)
            {
                searchNextSibling.add(current.sibling);
            }
            if (current.child != null)
            {
                searchNextChildren.add(current.child);
            }

        }
        Queue<Node> tempQueue = new ArrayDeque<Node>();
        while (!searchNextChildren.isEmpty())
        {
            Node current = (test.Node) searchNextChildren.remove();
            if (current.data == true)
            {
                return current;
            }
            if (current.sibling != null)
            {
                searchNextSibling.add(current.sibling);
            }
            if (current.child != null)
            {
                tempQueue.add(current.child);
            }

        }
        searchNextChildren.addAll(tempQueue);

    }
    return null;
}

Answer 1

这是用 C# 编写的更简洁的解决方案，但几乎与 java 相同：

    private Node VisitSiblings(Node node, Queue<Node> q)
{
    if (node == null || node.Flag) return node;
    q.Enqueue(node);                           
    return VisitSiblings(node.Sibling, q);     
}

public Node ReturnFirstTrueNode(Node root)
{
    Queue<Node> q = new Queue<Node>();

    Node node = VisitSiblings(root, q);  
    if (node != null) return node;    
    while (q.Count > 0)
    {
        node = q.Dequeue();
        Node x = VisitSiblings(node.Child, q); 
        if (x != null) return x;  
    }
    return null;  
}