c++ - 我们可以使用前序或后序遍历而不是中序遍历将树转换为双向链表吗？

Question

使用中序遍历进行转换
这里我们以中序方式遍历树并将其左右指针更改为下一个和上一个。

// A C++ program for in-place conversion of Binary Tree to DLL
    #include <iostream>
    using namespace std;
    
/* A binary tree node has data, and left and right pointers */
struct node
{
    int data;
    node* left;
    node* right;
};

// A simple recursive function to convert a given Binary tree to Doubly
// Linked List
// root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked list
void BinaryTree2DoubleLinkedList(node *root, node **head)
{
    // Base case
    if (root == NULL) return;
// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static node* prev = NULL;

// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root->left, head);

// Now convert this node
if (prev == NULL)
    *head = root;
else
{
    root->left = prev;
    prev->right = root;
}
prev = root;

// Finally convert right subtree
BinaryTree2DoubleLinkedList(root->right, head);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* new_node = new node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}

/* Function to print nodes in a given doubly linked list */
void printList(node *node)
{
    while (node!=NULL)
    {
        cout << node->data << " ";
        node = node->right;
    }
}

/* Driver program to test above functions*/
int main()
{
    // Let us create the tree shown in above diagram
    node *root   = newNode(10);
    root->left   = newNode(12);
    root->right  = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);

    // Convert to DLL
    node *head = NULL;
    BinaryTree2DoubleLinkedList(root, &head);

    // Print the converted list
    printList(head);

    return 0;
}

如果面试官问是否可以以预购或后购方式列出清单。答案是什么？
如果是，那怎么办？
我认为我们可以以预排序的方式遍历树并从中创建一个双向链表。可我怎么跟她解释。

标签： c++treedoubly-linked-listtree-traversalpreorder