将BST转换为前置和后置链接列表。

Question

这是第二轮亚马逊访谈question.Convert，一种给定的二进位搜索树，进入订单前和订单后链接列表，这种转换必须是inplace。

Answer 1

下面的代码是为了在不使用堆栈的情况下以预顺序遍历形式对二叉树进行平展。它采用预序遍历递归方法.在这种情况下，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);
   }

Answer 2

要解决预购版本的问题，您可以稍微修改一个简单的预定(请参阅下面的代码)。

这样做的目的是从二进位搜索树中构造一个双链接的列表。但是，我们只在遍历过程中设置前向链接。

让我们通过一个例子来学习。如果树看起来像：

        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;
}

Answer 3

void preorder(struct node *head)
{

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

在addToLL()中，您可以继续将节点添加到链接列表中。

全球宣言

struct node *llHead;

这样链表头就完好无损了。