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

思路:
1.利用中序遍历，TOP24 题解。因为二叉搜索树，左边的节点比根节点小，右边的节点比根节点大。所以排序的话不就是 左节点 根节点 右节点嘛，这不就是中序遍历树嘛
2.只需要得到了当前节点，我们保存前一个节点，每次将前一个节点的右节点指向当前节点，当前节点的左节点指向前一个节点即可，这就是双向链表了

import java.util.*;
/**
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 (pRootOfTree == null) {
            return null;
        }
        //中序遍历  左 根 右
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = pRootOfTree;
        TreeNode head = null, temp = null;
        while (!stack.isEmpty() || currentNode != null) {
            //寻找到所有左分支上的所有节点，入栈
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            //左分支上的最后一个节点
            currentNode = stack.pop();
            //如果temp是空的，说明第一次遍历 设置一下头节点
            if (temp == null) {
                temp = currentNode;
                head = temp;
            } else {
                //否则的话 当前节点的左节点，指向上一个节点，上一个节点的右节点指向当前节点
                currentNode.left = temp;
                temp.right = currentNode;

                temp = currentNode;
            }
            currentNode = currentNode.right;
        }
        return head;
    }
}