二叉搜索树与双向链表

做这道题目折腾了半天，最后问题出在极其低端的问题上，后面详细说明。

看到二叉搜索树，还有升序排列，首先想到的是中序遍历二叉搜索树，使用非递归的中序遍历，没有什么特别大的难度：

import java.util.*;
public class Solution {
    public TreeNode Convert(TreeNode root) {
        if (root == null) 
            return null;
        Stack<TreeNode> s = new Stack<>();
        TreeNode head = null, p = null;
        while (root != null || !s.isEmpty()) {
            if (root != null) {
                s.push(root);
                root = root.left;
            } else {
                root = s.pop();
                if (p == null) {
                    head = root;
                } else {
                    p.right = root;
                }
                root.left = p;
                p = root;
                root = root.right;
            }
        }
        return head;
    }
}

主要就是构建链表的时候需要初始化首节点和使用一个指针去向后不断构建链表，也可以使用额外的头节点，只不过返回的时候要返回头节点的下一个节点，还要把头节点后一个节点到头节点的左指针给断了。

后来就想使用递归的方式进行一下求解，于是问题就来了。

我写递归的风格是一般不使用Java类的成员变量，而是通过递归辅助函数的参数进行传参，而问题就出在这里。

先看一个使用成员变量存储链表节点的正确解：

public class Solution {
    TreeNode head, pre; // 使用成员变量存储，相当于全局变量

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        dfs(pRootOfTree);
        return head;
    }
    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if(pre != null)
            pre.right = root;
        else 
            head = root;
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}

而我自己写了一个递归：

import java.util.*;
public class Solution {
    public TreeNode Convert(TreeNode root) {
        TreeNode h = new TreeNode(-1), p = head;
        doConvert(root, p);
        p = h.right;
        p.left = null;
        return p;
    }

    private void doConvert(TreeNode root, TreeNode p) {
        if (root == null) {
            return ;
        }
        doConvert(root.left, p);
        p.right = root;
        root.left = p;
        p = p.right;
        doConvert(root.right, p);
    }
}

感觉上好像没什么问题，但是怎么都无法AC，这里还是我习惯的使用方法参数传参的方式，而问题就出在这里，假设一棵二叉搜索树：

        4
       / \
      2   5
     / \
    1   3

我们递归调用的时候，先一直向左，处理1节点，1节点的处理是没有问题的，这个时候我额外声明了一个头节点，头节点和1之间的维护是正确的，1节点处理完成后返回，开始处理其父节点2，问题就出现在这里，由于我使用的是方法参数传参，因此是值传递，1的处理逻辑中将p = p.right看起来好像是把前导指针向后移动了一位，然后构建链表的下一个节点，但是那是在1的递归栈中，等到返回到2的递归栈中时，使用的p还是递归调用传给1的p，而不是1处理完成后的p，这也是根本问题所在，可见使用成员变量做全局参数在这种场景下确实很方便。

但是这种思路是不是就没有办法了呢，也不是：

public class Solution {

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) 
            return null;
        TreeNode head = new TreeNode(-1), pre = head;
        dfs(pRootOfTree, pre);
        pre = head.right;
        pre.left = null;
        return pre;
    }
    public TreeNode dfs(TreeNode root, TreeNode pre) {
        if(root == null)
            return pre;

        pre = dfs(root.left, pre);

        pre.right = root;
        root.left = pre;
        pre = pre.right;

        pre = dfs(root.right, pre);
        return pre;
    }
}

这个解的写法是在使用方法参数传参的基础上，每次递归调用后将更新后的pre指针进行传递或返回，从而实现不声明全局变量，但是通过传参实现全局变量的效果。

折腾了半天对递归中的值传递有了进一步认识，如果是整个递归过程操作同一个引用，如List对象，然后不同的递归层级是向同一个List对象中添加/删除值，那么使用方法传参可以免去全局变量的声明，在整个递归过程中操作同一个对象。而如果在递归过程中操作的对象引用发生了变化，如这个例子中的构建链表时的前导指针pre，且这个值会影响下一级递归或上层返回结果，那么使用成员变量做全局参数不失为一种简单的方法，当然也可以每次递归的时候返回修改后的结果，只不过递归函数看起来没有那么的直观。

有自己的风格是一种特色，但是不能抱残守缺，如果发现自己现有的模式不能很好地解决问题，有进一步提升的空间，还是要敢于突破自己，不断优化精进，寻找更加有效的解决方案。