二叉搜索树与双向链表

题目描述

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

思路：中序遍历的节点顺序转为双向链表

中序遍历将left连接上前驱节点，最后倒序遍历更新right为后驱节点顺便找到链表头部

public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = pRootOfTree;
        TreeNode pre = null;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node.left = pre;
            pre = node;
            node = node.right;
        }
        while (pre.left != null) {
            pre.left.right = pre;
            pre = pre.left;
        }
        return pre;
    }
}