题解 | #二叉搜索树与双向链表#

非递归（中序遍历）,二叉搜索树的中序遍历就是得到它的从小到大排序数列，只需要在每个节点进行树结构和双向链表的转换就可以了，注意：要保存好头节点！

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

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

    }

}
*/
import java.util.Stack;
public class Solution {
    private TreeNode cur = null;    //遍历的当前节点
    private TreeNode head = null;    //生成链表的头节点
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)    return null;
        //非递归（中序遍历）
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = pRootOfTree;
        TreeNode pre = null;
        //寻找链表头节点
        while(p != null){
                stack.push(p);
                p = p.left;
            }
        p = stack.pop();
        //赋值链表头节点
        pRootOfTree = p;
        pre = p;
        p = p.right;
        //中序遍历树节点
        while(p != null || !stack.isEmpty()){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            //节点转化
            p.left = pre;
            pre.right = p;
            pre = p;
            //更新当前节点
            p = p.right;
        }
        return pRootOfTree;
    }
}

这样再原树结构上操作，空间复杂度为O(1), 遍历树的所有节点，时间复杂度为O(n),相比较递归的方法更优，不需要额外的空间保存递归调用栈。