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

import java.util.Stack;

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

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

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 如果这棵树是空的，或者这棵树只有一个根节点，那么直接返回即可
        if (null == pRootOfTree || (null == pRootOfTree.left && null == pRootOfTree.right)) {
            return pRootOfTree;
        }
        // 中序遍历
        // 定义一个栈，用于存放节点
        Stack<TreeNode> st = new Stack<>();
        // 定义一个队列，用于存放节点
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 定义一个辅助节点
        TreeNode tmp = pRootOfTree;
        // 定义一个头节点，用于最终的返回
        TreeNode head = null;
        // 初始化
        while (null != tmp) { // 将当前树的最左边的节点全部压到栈里去
            st.push(tmp);
            tmp = tmp.left;
        }
        tmp = pRootOfTree;
        while (!st.isEmpty()) { // 栈不为空
            tmp = st.pop(); // 弹出一个节点
            
            // 具体逻辑代码
            queue.add(tmp); // 将弹出的节点放入到队列当中去，方便我们后续的使用
            
            if (null != tmp.right) { // 如果以当前节点为根节点的树的有右子树，那么就将右子树的最左边的节点全部压到栈里去
                tmp = tmp.right;
                while (null != tmp) {
                    st.push(tmp);
                    tmp = tmp.left;
                }
            }
        }
        // 我们再定义一个辅助节点
        TreeNode tmpN = null;
        // 此时，队列中存放了所有的节点，并且它们都已经排好序了
        head = queue.poll();
        tmpN = head;
        tmpN.left = null; // 对于头节点来说，左指针应该为空
        while (!queue.isEmpty()) { // 队列不为空
            tmp = queue.poll(); // 用 tmp 去接住这个弹出来的节点
            tmpN.right = tmp; // tmpN 的右指针指向的是 tmp
            tmp.left = tmpN; // tmp 的左指针指向的是 tmpN
            tmp.right = null; // tmp 的右指针此时应该为空
            tmpN = tmp; // 别忘了将tmpN 移动到 tmp 当前位置上
        }
        return head;
    }
}