26 二叉搜索树与双向链表

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

代码一

非递归方法
思想:将中序遍历(左根右)的数据压缩到栈中,然后每次取出栈顶元素作为当前节点关联到上一个节点

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return null;
        //用栈去保存要遍历的路径
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = pRootOfTree;
        TreeNode pre = null;//用来存放中序遍历 的上一节点
        Boolean isFirst = true;
        while(p!=null||!stack.isEmpty())
        {
            //遍历左子树
            while(p!=null)
            {
                stack.push(p);
                p=p.left;
            }
            p=stack.pop();
            if(isFirst) {//将中序遍历的第一个节点标记为pRootOfTree;
                pRootOfTree = p;
                pre = pRootOfTree;
                isFirst = false;
            }else
            {
                pre.right = p;
                p.left = pre;
                pre = p;
            }
            p=p.right;
        }    
        return pRootOfTree;
    }
}

代码二

递归方法
思想:中序遍历的递归

public class Solution {
    TreeNode pre = null;
    TreeNode root = null;
    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;
    }
}

代码三

思想:
中序遍历二叉树，然后用一个ArrayList类保存遍历的结果，这样在ArratList中节点就按顺序保存了，然后再来修改指针

import java.util.ArrayList;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
       ArrayList<TreeNode> list=new ArrayList<>();
       Convert(list,pRootOfTree);
       return Convert(list);
    }
    public void Convert(ArrayList<TreeNode>list,TreeNode root){
        if (root!=null){
            Convert(list,root.left);
            list.add(root);
            Convert(list,root.right);
        }
    }
    public TreeNode Convert(ArrayList<TreeNode> list){
        TreeNode head=list.get(0);
        TreeNode cur=head;
        for (int i=1;i<list.size();++i){
            TreeNode node=list.get(i);
            node.left=cur;
            cur.right=node;
            cur=node;
        }
        return head;
    }
}