2

これは、ラウンド 2 の Amazon インタビューの質問です。特定の二分探索ツリーを事前注文および事後注文のリンク リストに変換します。この変換は適切に行う必要があります。

4

5 に答える 5

3

以下のコードは、スタックを使用せずにバイナリ ツリーをプレオーダー トラバーサル形式でフラット化するように記述されています。pre-Order トラバーサル再帰アプローチを使用します。この中で、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);
   }
于 2016-07-03T11:58:18.293 に答える
1

問題の予約注文バージョンを解決するには、単純な予約注文を少し変更します (以下のコードを参照してください)。

アイデアは、プレオーダー トラバーサルでバイナリ サーチ ツリーから双方向リンク リストを構築することです。ただし、トラバーサル中に前方リンクのみを設定します。

例を通して学びましょう。ツリーが次のようになっている場合:

        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;
}
于 2014-07-29T08:38:23.800 に答える
0

以下のアルゴリズムは、予約注文の変換用です。同様に、ポストオーダーを行うことができます。

 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;
于 2014-08-04T13:36:36.543 に答える
0 
void preorder(struct node *head)
{

if (head)
    {
        addToLL(head->data);
        preorder(head->left);
        preorder(head->right);
    }
}

addToLL() では、リンクされたリストにノードを追加し続けることができます。

グローバル宣言

struct node *llHead;

リンクされたリストの頭が無傷であるように。

于 2014-07-28T12:53:56.163 に答える