题目大意

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

分析

比较好想到的做法是利用中序遍历，这样去遍历二叉搜索树可以得到有序的序列。考察二叉树的非递归中序遍历。
第二种方法是利用递归，将树分为三个部分：根，左子树，右子树。对某部分子树的处理，总是返回这部分子树组成双向链表的最后一个结点lastNode。

image.png

代码一:递归

public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;

        TreeNode lastNodeInList = null;
        TreeNode pHead = Convert(pRootOfTree,lastNodeInList);
        
        while(pHead!=null && pHead.left!=null)   //注意null越界问题
            pHead = pHead.left;
        return pHead;

    }
    private TreeNode Convert(TreeNode root,TreeNode lastNodeInList) {
        if(root == null) return root;
        
        if(root.left!=null)
            lastNodeInList = Convert(root.left,lastNodeInList);   //更新了lastNodeInList记得返回
      
         /*这里做双向连接*/
        root.left = lastNodeInList;
        if(lastNodeInList!=null)
            lastNodeInList.right = root;

        lastNodeInList = root;
        if(root.right!=null)
            lastNodeInList = Convert(root.right,lastNodeInList);
        return lastNodeInList;
    }  

代码二：中序遍历

考察二叉树非递归中序遍历，把模板记牢。

public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        TreeNode pre = null;
        TreeNode cur = pRootOfTree;
        Stack<TreeNode> s = new Stack<>();
        while(!s.isEmpty() || cur!=null) {   //注意大循环跳出的条件，统一初始的情况
            if(cur!=null) {   //开始一直往左走
                s.push(cur);
                cur = cur.left;
            } else {
                cur = s.pop();
               /*这里开始做对应的细节处理*/
                if(pre == null) pre = cur;
                else {
                    cur.left = pre;
                    pre.right = cur;
                    pre = cur;
                }
                cur = cur.right;  
            }
        }

        while(pRootOfTree.left!=null) pRootOfTree = pRootOfTree.left;
        return pRootOfTree;
    }