linked-list - 树遍历，从树的预排序生成一个链表并为其编写测试用例

Question

我正在寻找以下问题的最佳解决方案。

给定一棵二叉树，我们需要使用前序遍历从树中生成一个链表。还要写一个测试用例来检查它是否正确。

如果您可以提供特定于生成链表和测试的解决方案。此外，该解决方案可以实现的最佳复杂性是什么。

我尝试过这样的事情：

public void TraversePreOrder(TreeNode node, LinkedListNode head){

    if(node != null) return;

    //Insert current node into linkedList 
    head = insertNodeIntoLinkedList(head, node.data);
    PreOrder(node.left, head);
    PreOrder(node.right, head);
}


public LinkedListNode insertNodeIntoLinkedList(LinkedListNode head, int data){

    LinkedListNode newNode = new LinkedListNode(data);
    if(head == null) {
        head = newNode;
        return head;
    }

    Node currentNode = head;
    while(currentNode.next != null){
        currentNode = currentNode.next;
    }

    currentNode.next = newNode;
    return head;

}     

Answer 1

通常以任何遍历顺序，我们从屏幕上遇到的节点打印数据。但是，您可以轻松地将打印功能替换为插入功能。

创建一个链表和一个函数来在你的链表中插入数据。然后创建你的树，从用户那里输入数据（如果这是你想要的），然后创建一个用于预订遍历的函数，而不是在屏幕上打印日期，你可以将它添加到你的链接列表中。