【剑指offer】二叉搜索树与双向链表-非递归实现

二叉搜索树的中序遍历就是有序序列，因此对二叉搜索树进行中序遍历，将中序遍历的当前节点与前一个节点进行连接。本解法使用栈完成非递归的遍历。

public static TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        TreeNode head = pRootOfTree;
        TreeNode tmp = null;
        Stack<TreeNode> stack = new Stack<>();
        while (head != null || !stack.empty()) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                TreeNode pop = stack.pop();
                head = pop;
                if (tmp != null) {
                    tmp.right = pop;
                }
                pop.left = tmp;
                tmp = pop;
                head = head.right;
            }
        }
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp;
    }