Как избежать статических переменных в рекурсиях

Question

Мой узел дерева определен как:

class Node{
int data;
Node left,right;
Node(int d)
{
    data=d;
    left=null;
    right=null;
}
}

Я пишу код для построения двойного связанного списка (nodes in which should be in the inorder traversal of the given tree) из двоичного дерева.

мой вопрос как работает второй метод . Я не получил его. Я хочу знать, как он работает (я кодировал метод 2, основываясь на некоторых других примерах)

Я подошел к нему двумя способами:

1) Использование статической переменной prev (для поддержки предыдущего узла)

2) Не используя его (использовал класс)

метод-1 выглядит следующим образом:

//method-1
static Node previous=null,head=null;     
Node Btree2DLL(Node n) /
{
    if(n==null)
        return n;
    Btree2DLL(n.left);
    if(previous==null)
    {
        head=n;
    }
    else
    {
        previous.right=n;
        n.left=previous;
    }
    previous=n;
    Btree2DLL(n.right);
    return head;
}

метод-2 выглядит следующим образом:

//method-2
class PreviousandHead
{
    Node HEADOFDLL,PREV;
}
Node Tree2DLL(Node n)
{
    PreviousandHead p=new PreviousandHead();
    return Btree2DLL(n,p);  
}

Node Btree2DLL(Node n,PreviousandHead p)
{   
    if(n==null)
        return n;
    Btree2DLL(n.left,p);
    if(p.PREV==null)
    {
        p.HEADOFDLL=n;
    }
    else
    {
        p.PREV.right=n;
        n.left=p.PREV;
    }
    p.PREV=n;
    Btree2DLL(n.right,p);
    return p.HEADOFDLL;
}

Ранее я пытался передать аргументы в методе-2, не создавая класс PreviousandHead как:

Node B2DLL(Node n)
{
    return Btree2DLL(n,null,null);  
}

Node Btree2DLL(Node n,Node previous,Node head)
{
if(n==null)
        return n;
    Btree2DLL(n.left,Node previous,Node head);
    if(previous==null)
    {
        head=n;
    }
    else
    {
        previous.right=n;
        n.left=previous;
    }
    previous=n;
    Btree2DLL(n.right,Node previous,Node head);
    return head;
}

это не сработало. Думаю, они каждый раз создают новые экземпляры.

Answer 1

Кажется, что второй метод будет работать, но последний метод не будет работать. Причина в том, что в последнем методе вы передаете копию ссылки на узел (параметры previous и head). Из-за этого вызывающая сторона не увидит изменения previous и head в вызываемом методе.

Подробнее об этом вы можете прочитать в статье https://www.javaworld.com/article/2077424/learn-java-does-java-pass-by-reference-or-pass-by-value.html

Я думаю, ваш код будет работать, если вы измените типы параметров previous и head с Node на AtomicReference<Node>

    Node b2DLL(Node n)
    {
        return btree2DLL(n, new AtomicReference<>(), new AtomicReference<>());
    }

    Node btree2DLL(Node n, AtomicReference<Node> previous, AtomicReference<Node> head)
    {
        if(n == null)
            return n;
        btree2DLL(n.left, previous, head);
        if(previous.get() == null)
        {
            head.set(n);
        }
        else
        {
            previous.get().right = n;
            n.left = previous.get();
        }
        previous.set(n);
        btree2DLL(n.right, previous, head);
        return head.get();
}

В мире Java считается, что имя метода начинается со строчной буквы.