题解 | #二叉搜索树与双向链表#

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode root;
    TreeNode pre;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        Convert(pRootOfTree.left);
        if(root==null) root = pRootOfTree;
        if(pre!=null){
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
        }
        pre = pRootOfTree;
        Convert(pRootOfTree.right);

        return root;
    }
}

这题目有两个难点：

1，首先是中序遍历时，左节点要把right指针指向根，右节点要把left指针指向根，这在递归时不能采用统一操作

2，引入一个冗余操作，可以解决这个问题

另外，总结一个经验：在解决递归的参数传递的时候，可以将变量定义在递归函数外，这样就可以解决，这在上一题中也有体现