二叉搜索树与双向链表

解题思路一：

/**
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; // 子递归返回的还是头指针，不要紧}
}