多种方法解决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);}

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

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

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

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

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

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

这样，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 引用。