剑指offer21 JZ36 二叉搜索树与双向链表

题目要求生成的双向链表，是二叉搜索的中序遍历结果（从小到大的顺序），对遍历的结果修改左右结点指向。 具体的指针变化，如图 树结构指针，叶子结点的左右指针指向都为空；
生成的双向链表结点指针；

1. 第一次
2. 第二次

解题思路 变种的中序的遍历

1. 使用二叉树的中序遍历可以获得一个要求链表结点的访问顺序；
2. 在这个顺序中，我们要存储当前的结点cur和访问前的结点pre（cur的值一定是比pre小的），
3. 修改pre和cur的左右指向，cur.right = pre; pre.left = cur;

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

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

    }

}
*/
import java.util.*;
public class Solution {
  TreeNode cur=null;
    TreeNode head=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        Convert(pRootOfTree.left);
        if(cur==null){
            //此时为最左节点  也就是头节点
            head=pRootOfTree;//保存头节点 
            cur=pRootOfTree;//记录头节点 方便操作
        }else{
            //不是最左节点（修改指向）
           cur.right=pRootOfTree;
           pRootOfTree.left=cur;
            cur=pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}