二叉搜索树与双向链表

解题思路一：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }
}
*/
// 一定要用自己的理解真正弄出来才行，否则没有用！
// 再次提醒，计算机这种工科性质的东西，死记硬背就是在浪费时间!
// 这道题目本质是在考察二叉树的中序遍历 + 双向链表插入 + 常量引入技巧 TAGS
// 本质上其实是一种模板。
public class Solution {
    // 全局变量
    private TreeNode tail = null; // 辅助常量用来连接使用。
    private TreeNode head = null;
    
    public TreeNode Convert(TreeNode root) {
        
        if(root != null){
            Convert(root.left);
            // 中间是对每一个遍历到的Node的处理，不断构建二叉链表即可,中序遍历中root指的是每一个节点！！！！要理解这个！！！
            if(tail == null && head == null){// 初始化
                head = root;
                tail = root; // 这里叶子最左边就固定了两个指针（都不用循环去找）
            }else{
                root.left = tail;
                tail.right = root; // 这里的顺序不要紧
                tail = root; // 更新最重要的tail指针
            }
            Convert(root.right);
        }
        return head; // 子递归返回的还是头指针，不要紧
    }
}