Конвертировать BST в списки ссылок по предварительному заказу и по предварительному заказу
Это круглый вопрос для интервью с Amazon. Преобразуйте данное дерево бинарного поиска в списки, связанные с предварительным заказом и после заказа, и это преобразование должно быть на месте.
5 ответов
Ниже приведен код для выравнивания двоичного дерева в форме обхода предварительного заказа без использования стека. Используется рекурсивный подход обхода предзаказа. В этом случае TreeNode[] arr будет содержать значение последнего левого узла, для которого я обновляю правый указатель этого узла.
public TreeNode preorderNode(TreeNode root,TreeNode[] arr)
{
if(root==null)
return null;
if(root!=null && root.left==null && root.right==null)
{
arr[0]=root;
return root;
}
TreeNode temp=root.right;
if(root.left!=null)
root.right=preorderNode(root.left,arr);
else arr[0]=root;
root.left=null;
arr[0].right=preorderNode(temp,arr);
return root;
}
public void flatten(TreeNode root) {
if(root==null || (root.left==null && root.right==null))
return;
TreeNode temp=root.right;
TreeNode[] arr=new TreeNode[1];
arr[0]=null;
if(root.left!= null)
root.right=preorderNode(root.left,arr);
else
arr[0]=root;
root.left=null;
arr[0].right=preorderNode(temp,arr);
}
Чтобы решить проблему с предварительным заказом, вы можете слегка изменить простой предварительный заказ (см. Код ниже, чтобы увидеть это).
Идея состоит в том, чтобы построить двусвязный список из двоичного дерева поиска в обходе предзаказа. Однако мы только устанавливаем прямые ссылки во время обхода.
Давайте учиться на примере. Если дерево выглядит так:
4
/ \
2 6
/ \ / \
1 3 5 7
Тогда связанный список должен выглядеть так:
4 <-> 2 <-> 1 <-> 3 <-> 6 <-> 5 <-> 7.
Теперь мы только устанавливаем прямые ссылки во время обхода предварительного заказа. Поэтому наш список будет выглядеть так.
4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7
Левый или предыдущий указатели (не показаны выше) остаются такими же, как в дереве. Теперь мы можем установить левые указатели с помощью простого обхода списка.
Код ниже делает именно это.
#include <iostream>
using namespace std;
class node{
public:
int data;
node * left, *right;
node(int a){
data = a;
left = right = NULL;
}
};
node * head = NULL, *prev = NULL;
void preorder(node * root){
if(!root) return;
//both head and prev aren't set. This node must be the root(and head of our required list).
if(!head and !prev) head = root;
//store the address of root's right child
node * temp = root->right;
/*
If prev is set, make current node it's right child.
(This is why we save right child's address for every node in temp.)
*/
if(prev) prev->right = root;
//now make the current node prev.
prev = root;
cout << root ->data <<" ";
preorder(root->left);
preorder(temp);
}
void printll(){
node * prev = NULL;
while(head != NULL){
cout << head ->data << " ";
head -> left = prev;
head = head -> right;
prev = head;
}
cout<<endl;
}
int main() {
node * t = new node(4);
t->left = new node(2);
t->left->left = new node(1);
t->left->right = new node(3);
t->right = new node(6);
t->right->left = new node(5);
t->right->right = new node(7);
preorder(t);
cout<<endl;
printll();
return 0;
}
void preorder(struct node *head)
{
if (head)
{
addToLL(head->data);
preorder(head->left);
preorder(head->right);
}
}
В addToLL() вы можете просто добавлять узлы в связанный список.
Глобальная Декларация
struct node *llHead;
Так что заголовок связанного списка не поврежден.
Приведенный ниже алгоритм предназначен для преобразования предварительного заказа. Точно так же вы можете сделать пост-заказ.
struct node
{
int data;
struct node* left;
struct node* right;
};
/Algorithm */
struct node* bintree2listHelper(struct node *root)
{
if (root == NULL)
return root;
if (root->left != NULL)
{
struct node* left = bintree2listHelper(root->left);
int flag =0;
if(left->left == NULL)
{
left->left = left->right;
}
for(;left->left != NULL;)
{
struct node *temp = left;
for (; temp->right!=NULL; )
{
flag = 1;
temp=temp->right;
}
if(flag)
{
temp->left = root->right;
left =left->left;
break;
}
else
{
left =left->left;
}
}
if(!flag)
left->left = root->right;
}
if (root->right!=NULL)
{
struct node* right = bintree2listHelper(root->right);
struct node *temp1= right;
for (; right->left!=NULL; )
{
temp1 =right;
right = right->left;
}
right->left = temp1->right;
}
return root;
}
struct node* bintreeTolist(struct node *root)
{
if (root == NULL)
return root;
root = bintree2listHelper(root);
return (root);
}
struct node* newNode(int data)
{
struct node* new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = data;
new_node->left = new_node->right = NULL;
return (new_node);
}
void printList(struct node *node)
{
while (node!=NULL)
{
printf("%d ", node->data);
node = node->left;
}
printf("\n");
}
int main()
{
typedef struct node node;
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);
root->left->right->left = newNode(78);
root->left->right->right = newNode(77);
node *head = bintreeTolist(root);
// Print the converted list
printList(head);
return 0;
Предварительный заказ Связанный список
public TreeNode flatten(TreeNode root) {
if(root==null)
return null;
Stack<TreeNode> s=new Stack<TreeNode>();
s.add(root);
while(!s.isEmpty()){
root=s.pop();
if(root.right!=null)
s.add(root.right);
if(root.left!=null)
s.add(root.left);
if(!s.isEmpty())
root.right=s.peek();
else
root.right=null;
root.left=null;
}
return root;
}
Приведенный выше код дает связанный список предварительного заказа с правым указателем, действующим в качестве следующего указателя, а левый указатель игнорируется (т. Е. Устанавливается в ноль). Это небольшая модификация итеративного кода обхода предварительного заказа.
Идея состоит в том, что, как только обработка текущего узла будет завершена, на вершине стека будет следующий узел текущего узла в связанном списке.