多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表， 同时弄透引用变更带来的bug

1 描述

2 解法一: 使用list列表粗出中序遍历的结果，然后再依次处理list中的元素并且双向链接

public Node treeToDoublyList2(Node root) {
        if(root==null)return root;
        Node dummy=new Node(-10000);

        List<Node>ans=new ArrayList<>();

        dfs2(root,ans);
        Node pre=ans.get(0);
        dummy.right=pre;

        for(int i=1;i<ans.size();i++){
            Node cur=ans.get(i);
            pre.right=cur;
            cur.left=pre;
            pre=cur;
        }
        dummy.right.left=pre;
        pre.right=dummy.right;
        return dummy.right;
    }
     void dfs2(Node root, List<Node>ans){
        if(root==null){
            return;
        }
        dfs2(root.left,ans);
        ans.add(root);
        dfs2(root.right,ans);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3 解法二：使用一个全局变量作为前驱节点，同时使用一个虚拟头节点指向这个前驱，在使用dfs的时候进行双向链接，然后通过dummy虚拟头节点完成链表循环

	Node pre;
    public Node treeToDoublyList(Node root) {
        if(root==null)return root;
        Node dummy=new Node(-10000);
        pre=dummy;
        dfs(root);
        pre.right=dummy.right;
        dummy.right.left=pre;
        return dummy.right;
    }

    void dfs(Node root){
        if(root==null){
            return;
        }
        dfs(root.left);
        pre.right=root;
        root.left=pre;
        pre=root;
        dfs(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4 解法三：通过引用传递

4.1 版本一：数组引用传递（执行无误）

    public Node treeToDoublyList(Node root) {
        if(root==null)return root;
        Node dummy=new Node(-10000);
        Node prev[]=new Node[1];
        prev[0]=new Node(100001);
        dummy=prev[0];
        dfs4(root,prev);
        prev[0].right=dummy.right;
        dummy.right.left=prev[0];
        return dummy.right;
    }
    void dfs4(Node root,Node[] prev){
        if(root==null){
            return;
        }
        dfs4(root.left,prev);
        prev[0].right=root;
        root.left=prev[0];
        prev[0]=root;
        dfs4(root.right,prev);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.2 版本二：通过变量引用传递（但是执行起来有问题）

    public Node treeToDoublyList(Node root) {
        if(root==null)return root;
        Node dummy=new Node(-10000);
        Node pre=dummy;
        dfs(root);
        pre.right=dummy.right;
        dummy.right.left=pre;
        return dummy.right;
    }

    void dfs3(Node root,Node pre){
        if(root==null){
            return;
        }
        dfs3(root.left,pre);
        pre.right=root;
        root.left=pre;
        pre=root;
        dfs3(root.right,pre);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.3 比较一下版本1和2，2中哪里出错了，为什么错了？

这段代码实际上是一个常见的算法题目的解法，目标是将一个二叉搜索树转换为一个排序的双向链表。整个过程是通过中序遍历来实现的，遍历过程中修改节点的左右指针来构建双向链表。代码中使用了一个额外的节点 dummy 来帮助构建双向链表，并使用 pre 节点来保存前一个遍历到的节点。

代码中的错误主要在 dfs3 方法中，pre 节点作为参数传递，但在递归调用中并没有更新 pre 的值。这会导致链表构建不正确。要修复这个问题，你需要在 dfs3 方法中更新 pre 的值。下面是修正后的 dfs3 方法：

void dfs3(Node root,Node[] pre){
    if(root==null){
        return;
    }
    dfs3(root.left,pre);
    pre[0].right=root;
    root.left=pre[0];
    pre[0]=root;
    dfs3(root.right,pre);
}
1
2
3
4
5
6
7
8
9
10

调用 dfs3 方法时，你需要传递一个 Node 类型数组作为 pre 参数，例如：

Node[] pre = new Node[1];
pre[0] = dummy;
dfs3(root, pre);
1
2
3

这样，pre 数组中的元素会在 dfs3 方法中被正确更新，从而可以构建正确的双向链表。

4.4 这里的Node pre是作为值传递的嘛？你改为传递长度为1的Node数组，就变成了引用传递？

在Java中，对象的引用是通过值传递的。这意味着当你将一个对象作为参数传递给一个方法时，你实际上是将对象引用的副本传递给了方法。如果你在方法内部修改引用所指向的对象的状态，这个修改会反映到方法外部。但是，如果你尝试直接修改引用本身（例如，使其指向一个新的对象），这个修改不会影响到方法外部的引用。

在你的代码中，Node pre 是一个对象引用，当你将其作为参数传递给 dfs3 方法时，你传递的是引用的副本。在 dfs3 方法内部，你可以修改 pre 引用所指向的 Node 对象的状态，但是如果你尝试直接修改 pre 引用本身（例如，pre = new Node(…), pre = root），这个修改不会影响到方法外部的 pre 引用。

为了在 dfs3 方法内部更新外部的 pre 引用，你可以使用一个 Node 类型的数组，如我之前所示。数组在Java中是一个对象，当你将数组作为参数传递给一个方法时，你传递的是数组对象引用的副本。你可以在方法内部修改数组内容，这些修改会反映到方法外部。因此，你可以使用一个数组来包装 pre 引用，然后在 dfs3 方法内部更新数组的内容，这样就能够实现在方法调用后更新外部的 pre 引用。