剑指offer——26.二叉搜索树与双向链表

题目描述

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

思路：
利用栈，循环条件（p不为空||栈不为空）先一直压栈树的左节点，弹出栈顶，将其作为双向链表的ROOT，之后弹栈一个元素，更改前面定好的指针，使用pre指向当前节点之前的节点，p指向当前弹出元素，改变前后双向指针的顺序，之后p指向当前弹栈元素的右节点。
代码：

import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        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){
                root = p;
                pre = root;
                isFirst = false;
            }else{
                pre.right = p;
                p.left = pre;
                pre = p;
            }      
            p = p.right;
        }
        return root;
    }
}