この質問は、最近のコーディング インタビューで尋ねられました。
Q :与えられた二分木を二重連結リストに変換するプログラムを書きなさい。双方向リンク リスト内のノードは、ジグザグ レベルの順序トラバーサルによって形成された順序で配置されます。
私のアプローチ
私はいつでもツリーのジグザグレベルの順序トラバーサルを実行し、それを配列に格納してから、二重リンクリストを作成できます。しかし、問題はインプレース ソリューションを必要とします。再帰的アプローチを使用する必要があることを説明するのに誰か助けてもらえますか?
これは再帰的なアプローチです。ここで、rootは、形成されたリストの中間要素を指すことに注意してください。だから、頭を取得するためにルートから後方にトラバースするだけです。
#define NODEPTR struct node*
NODEPTR convert_to_ll(NODEPTR root){
if(root->left == NULL && root->right == NULL)
return root;
NODEPTR temp = NULL;
if(root->left != NULL){
temp = convert_to_ll(root->left);
while(temp->right != NULL)
temp = temp->right;
temp->right = root;
root->left = temp;
}
if(root->right != NULL){
temp = convert_to_ll(root->right);
while(temp->left != NULL)
temp = temp->left;
temp->left = root;
root->right = temp;
}
return root;
}
最も簡単な方法。単一の順序通りのトラバーサルで、O(1) スペースの複雑さだけでこれを実現できます。lastPointerという名前のポインターを保持し、すべてのノードにアクセスした後にそれを追跡します。左右を使う
public void toll(T n) {
if (n != null) {
toll(n.left);
if(lastPointer==null){
lastPointer=n;
}else{
lastPointer.right=n;
n.left=lastPointer;
lastPointer=n;
}
toll(n.right);
}
}
C++ コード:
Node<T> *BTtoDoublyLLZigZagOrder(Node<T> *root)
{
if (root == 0)
return 0;
if (root->mLeft == 0 && root->mRight == 0)
return root;
queue<Node<T> *> q;
q.push(root);
Node<T> *head = root;
Node<T> *prev = 0,*curr = 0;
while(!q.empty())
{
curr = q.front();
q.pop();
if (curr->mLeft)
q.push(curr->mLeft);
if (curr->mRight)
q.push(curr->mRight);
curr->mRight = q.front();
curr->mLeft = prev;
prev = curr;
}
return head;
}
スタンフォード ライブラリ リンクに記載されているソリューションは、BST から循環 DLL への完全なソリューションです。以下のソリューションは、BST から循環 DLL への正確な変換ではありませんが、DLL の端を結合することで循環 DLL を実現できます。ジグザグに並べられたツリーからdllへの変換とはまったく異なります。
注：この解決策は、BSTから循環DLLへの完全な変換ではありませんが、簡単に理解できるハックです
JAVA コード
public Node bstToDll(Node root ){
if(root!=null){
Node lefthead = bstToDll(root.left); // traverse down to left
Node righthead = bstToDll(root.right); // traverse down to right
Node temp = null;
/*
* lefthead represents head of link list created in left of node
* righthead represents head of link list created in right
* travel to end of left link list and add the current node in end
*/
if(lefthead != null) {
temp = lefthead;
while(temp.next != null){
temp = temp.next;
}
temp.next = root;
}else{
lefthead = root;
}
root.prev = temp;
/*
*set the next node of current root to right head of right list
*/
if(righthead != null){
root.next = righthead;
righthead.prev = root;
}else{
righthead = root;
}
return lefthead;// return left head as the head of the list added with current node
}
return null;
}
それが誰かを助けることを願っています
ヘッドとテールの 2 つのセンチネル ノードを使用して、ツリーを順番にトラバーサルします。最初に、頭を最小のノードに、またその逆にリンクし、最小のノードを尾に、またその逆にリンクする必要があります。初回以降は、トラバーサルが完了するまで current-node と tail を再リンクするだけです。トラバーサルの後、センチネル ノードを削除し、頭と尾を適切に再リンクします。
public static Node binarySearchTreeToDoublyLinkedList(Node root) {
// sentinel nodes
Node head = new Node();
Node tail = new Node();
// in-order traversal
binarySearchTreeToDoublyLinkedList(root, head, tail);
// re-move the sentinels and re-link;
head = head.right;
tail = tail.left;
if (head != null && tail != null) {
tail.right = head;
head.left = tail;
}
return head;
}
/** In-order traversal **/
private static void binarySearchTreeToDoublyLinkedList(Node currNode, Node head, Node tail) {
if (currNode == null) {
return;
}
// go left
//
binarySearchTreeToDoublyLinkedList(currNode.left, head, tail);
// save right node for right traversal as we will be changing current
// node's right to point to tail
//
Node right = currNode.right;
// first time
//
if (head.right == null) {
// fix head
//
head.right = currNode;
currNode.left = head;
// fix tail
//
tail.left = currNode;
currNode.right = tail;
} else {
// re-fix tail
//
Node prev = tail.left;
// fix current and tail
//
tail.left = currNode;
currNode.right = tail;
// fix current and previous
//
prev.right = currNode;
currNode.left = prev;
}
// go right
//
binarySearchTreeToDoublyLinkedList(right, head, tail);
}
inorder トラバーサルを使用して、以前にアクセスしたノードを追跡できます。訪問したすべてのノードに対して、前のノードの右と現在のノードの左を割り当てることができます。
void BST2DLL(node *root, node **prev, node **head)
{
// Base case
if (root == NULL) return;
// Recursively convert left subtree
BST2DLL(root->left, prev, head);
if (*prev == NULL) // first iteration
*head = root;
else
{
root->left = *prev;
(*prev)->right = root;
}
*prev = root; // save the prev pointer
// Finally convert right subtree
BST2DLL(root->right, prev, head);
}
node* convertToDLL(node* root, node*& head, node*& tail)
{
//empty tree passed in, nothing to do
if(root == NULL)
return NULL;
//base case
if(root->prev == NULL && root->next == NULL)
return root;
node* temp = NULL;
if(root->prev != NULL)
{
temp = convertToDLL(root->prev, head, tail);
//new head of the final list, this will be the left most
//node of the tree.
if(head == NULL)
{
head=temp;
tail=root;
}
//create the DLL of the left sub tree, and update t
while(temp->next != NULL)
temp = temp->next;
temp->next = root;
root->prev= temp;
tail=root;
}
//create DLL for right sub tree
if(root->next != NULL)
{
temp = convertToDLL(root->next, head, tail);
while(temp->prev != NULL)
temp = temp->prev;
temp->prev = root;
root->next = temp;
//update the tail, this will be the node with the largest value in
//right sub tree
if(temp->next && temp->next->val > tail->val)
tail = temp->next;
else if(temp->val > tail->val)
tail = temp;
}
return root;
}
void createCircularDLL(node* root, node*& head, node*& tail)
{
convertToDLL(root,head,tail);
//link the head and the tail
head->prev=tail;
tail->next=head;
}
int main(void)
{
//create a binary tree first and pass in the root of the tree......
node* head = NULL;
node* tail = NULL;
createCircularDLL(root, head,tail);
return 1;
}