避免递归中的静态变量

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

早些时候，我尝试在method-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世界中，它被认为是以小写开始一个方法名。